1/****************************************************************************
2**
3** Copyright (C) 2017 The Qt Company Ltd.
4** Copyright (C) 2018 Intel Corporation.
5** Contact: https://www.qt.io/licensing/
6**
7** This file is part of the QtCore module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial License Usage
11** Licensees holding valid commercial Qt licenses may use this file in
12** accordance with the commercial license agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and The Qt Company. For licensing terms
15** and conditions see https://www.qt.io/terms-conditions. For further
16** information use the contact form at https://www.qt.io/contact-us.
17**
18** GNU Lesser General Public License Usage
19** Alternatively, this file may be used under the terms of the GNU Lesser
20** General Public License version 3 as published by the Free Software
21** Foundation and appearing in the file LICENSE.LGPL3 included in the
22** packaging of this file. Please review the following information to
23** ensure the GNU Lesser General Public License version 3 requirements
24** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
25**
26** GNU General Public License Usage
27** Alternatively, this file may be used under the terms of the GNU
28** General Public License version 2.0 or (at your option) the GNU General
29** Public license version 3 or any later version approved by the KDE Free
30** Qt Foundation. The licenses are as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
32** included in the packaging of this file. Please review the following
33** information to ensure the GNU General Public License requirements will
34** be met: https://www.gnu.org/licenses/gpl-2.0.html and
35** https://www.gnu.org/licenses/gpl-3.0.html.
36**
37** $QT_END_LICENSE$
38**
39****************************************************************************/
40
41#include "qsemaphore.h"
42#include "qmutex.h"
43#include "qfutex_p.h"
44#include "qwaitcondition.h"
45#include "qdeadlinetimer.h"
46#include "qdatetime.h"
47
48QT_BEGIN_NAMESPACE
49
50using namespace QtFutex;
51
52/*!
53 \class QSemaphore
54 \inmodule QtCore
55 \brief The QSemaphore class provides a general counting semaphore.
56
57 \threadsafe
58
59 \ingroup thread
60
61 A semaphore is a generalization of a mutex. While a mutex can
62 only be locked once, it's possible to acquire a semaphore
63 multiple times. Semaphores are typically used to protect a
64 certain number of identical resources.
65
66 Semaphores support two fundamental operations, acquire() and
67 release():
68
69 \list
70 \li acquire(\e{n}) tries to acquire \e n resources. If there aren't
71 that many resources available, the call will block until this
72 is the case.
73 \li release(\e{n}) releases \e n resources.
74 \endlist
75
76 There's also a tryAcquire() function that returns immediately if
77 it cannot acquire the resources, and an available() function that
78 returns the number of available resources at any time.
79
80 Example:
81
82 \snippet code/src_corelib_thread_qsemaphore.cpp 0
83
84 A typical application of semaphores is for controlling access to
85 a circular buffer shared by a producer thread and a consumer
86 thread. The \l{Semaphores Example} shows how
87 to use QSemaphore to solve that problem.
88
89 A non-computing example of a semaphore would be dining at a
90 restaurant. A semaphore is initialized with the number of chairs
91 in the restaurant. As people arrive, they want a seat. As seats
92 are filled, available() is decremented. As people leave, the
93 available() is incremented, allowing more people to enter. If a
94 party of 10 people want to be seated, but there are only 9 seats,
95 those 10 people will wait, but a party of 4 people would be
96 seated (taking the available seats to 5, making the party of 10
97 people wait longer).
98
99 \sa QSemaphoreReleaser, QMutex, QWaitCondition, QThread, {Semaphores Example}
100*/
101
102/*
103 QSemaphore futex operation
104
105 QSemaphore stores a 32-bit integer with the counter of currently available
106 tokens (value between 0 and INT_MAX). When a thread attempts to acquire n
107 tokens and the counter is larger than that, we perform a compare-and-swap
108 with the new count. If that succeeds, the acquisition worked; if not, we
109 loop again because the counter changed. If there were not enough tokens,
110 we'll perform a futex-wait.
111
112 Before we do, we set the high bit in the futex to indicate that semaphore
113 is contended: that is, there's a thread waiting for more tokens. On
114 release() for n tokens, we perform a fetch-and-add of n and then check if
115 that high bit was set. If it was, then we clear that bit and perform a
116 futex-wake on the semaphore to indicate the waiting threads can wake up and
117 acquire tokens. Which ones get woken up is unspecified.
118
119 If the system has the ability to wake up a precise number of threads, has
120 Linux's FUTEX_WAKE_OP functionality, and is 64-bit, instead of using a
121 single bit indicating a contended semaphore, we'll store the number of
122 tokens *plus* total number of waiters in the high word. Additionally, all
123 multi-token waiters will be waiting on that high word. So when releasing n
124 tokens on those systems, we tell the kernel to wake up n single-token
125 threads and all of the multi-token ones. Which threads get woken up is
126 unspecified, but it's likely single-token threads will get woken up first.
127 */
128
129#if defined(FUTEX_OP) && QT_POINTER_SIZE > 4
130static Q_CONSTEXPR bool futexHasWaiterCount = true;
131#else
132static Q_CONSTEXPR bool futexHasWaiterCount = false;
133#endif
134
135static const quintptr futexNeedsWakeAllBit =
136 Q_UINT64_C(1) << (sizeof(quintptr) * CHAR_BIT - 1);
137
138static int futexAvailCounter(quintptr v)
139{
140 // the low 31 bits
141 if (futexHasWaiterCount) {
142 // the high bit of the low word isn't used
143 Q_ASSERT((v & 0x80000000U) == 0);
144
145 // so we can be a little faster
146 return int(unsigned(v));
147 }
148 return int(v & 0x7fffffffU);
149}
150
151static bool futexNeedsWake(quintptr v)
152{
153 // If we're counting waiters, the number of waiters is stored in the low 31
154 // bits of the high word (that is, bits 32-62). If we're not, then we use
155 // bit 31 to indicate anyone is waiting. Either way, if any bit 31 or above
156 // is set, there are waiters.
157 return v >> 31;
158}
159
160static QBasicAtomicInteger<quint32> *futexLow32(QBasicAtomicInteger<quintptr> *ptr)
161{
162 auto result = reinterpret_cast<QBasicAtomicInteger<quint32> *>(ptr);
163#if Q_BYTE_ORDER == Q_BIG_ENDIAN && QT_POINTER_SIZE > 4
164 ++result;
165#endif
166 return result;
167}
168
169static QBasicAtomicInteger<quint32> *futexHigh32(QBasicAtomicInteger<quintptr> *ptr)
170{
171 auto result = reinterpret_cast<QBasicAtomicInteger<quint32> *>(ptr);
172#if Q_BYTE_ORDER == Q_LITTLE_ENDIAN && QT_POINTER_SIZE > 4
173 ++result;
174#endif
175 return result;
176}
177
178template <bool IsTimed> bool
179futexSemaphoreTryAcquire_loop(QBasicAtomicInteger<quintptr> &u, quintptr curValue, quintptr nn, int timeout)
180{
181 QDeadlineTimer timer(IsTimed ? QDeadlineTimer(timeout) : QDeadlineTimer());
182 qint64 remainingTime = timeout * Q_INT64_C(1000) * 1000;
183 int n = int(unsigned(nn));
184
185 // we're called after one testAndSet, so start by waiting first
186 goto start_wait;
187
188 forever {
189 if (futexAvailCounter(v: curValue) >= n) {
190 // try to acquire
191 quintptr newValue = curValue - nn;
192 if (u.testAndSetOrdered(expectedValue: curValue, newValue, currentValue&: curValue))
193 return true; // succeeded!
194 continue;
195 }
196
197 // not enough tokens available, put us to wait
198 if (remainingTime == 0)
199 return false;
200
201 // indicate we're waiting
202start_wait:
203 auto ptr = futexLow32(ptr: &u);
204 if (n > 1 || !futexHasWaiterCount) {
205 u.fetchAndOrRelaxed(valueToAdd: futexNeedsWakeAllBit);
206 curValue |= futexNeedsWakeAllBit;
207 if (n > 1 && futexHasWaiterCount) {
208 ptr = futexHigh32(ptr: &u);
209 //curValue >>= 32; // but this is UB in 32-bit, so roundabout:
210 curValue = quint64(curValue) >> 32;
211 }
212 }
213
214 if (IsTimed && remainingTime > 0) {
215 bool timedout = !futexWait(futex&: *ptr, expectedValue: curValue, nstimeout: remainingTime);
216 if (timedout)
217 return false;
218 } else {
219 futexWait(futex&: *ptr, expectedValue: curValue);
220 }
221
222 curValue = u.loadAcquire();
223 if (IsTimed)
224 remainingTime = timer.remainingTimeNSecs();
225 }
226}
227
228template <bool IsTimed> bool futexSemaphoreTryAcquire(QBasicAtomicInteger<quintptr> &u, int n, int timeout)
229{
230 // Try to acquire without waiting (we still loop because the testAndSet
231 // call can fail).
232 quintptr nn = unsigned(n);
233 if (futexHasWaiterCount)
234 nn |= quint64(nn) << 32; // token count replicated in high word
235
236 quintptr curValue = u.loadAcquire();
237 while (futexAvailCounter(v: curValue) >= n) {
238 // try to acquire
239 quintptr newValue = curValue - nn;
240 if (u.testAndSetOrdered(expectedValue: curValue, newValue, currentValue&: curValue))
241 return true; // succeeded!
242 }
243 if (timeout == 0)
244 return false;
245
246 // we need to wait
247 quintptr oneWaiter = quintptr(Q_UINT64_C(1) << 32); // zero on 32-bit
248 if (futexHasWaiterCount) {
249 // increase the waiter count
250 u.fetchAndAddRelaxed(valueToAdd: oneWaiter);
251
252 // We don't use the fetched value from above so futexWait() fails if
253 // it changed after the testAndSetOrdered above.
254 if ((quint64(curValue) >> 32) == 0x7fffffff)
255 return false; // overflow!
256 curValue += oneWaiter;
257
258 // Also adjust nn to subtract oneWaiter when we succeed in acquiring.
259 nn += oneWaiter;
260 }
261
262 if (futexSemaphoreTryAcquire_loop<IsTimed>(u, curValue, nn, timeout))
263 return true;
264
265 if (futexHasWaiterCount) {
266 // decrement the number of threads waiting
267 Q_ASSERT(futexHigh32(&u)->loadRelaxed() & 0x7fffffffU);
268 u.fetchAndSubRelaxed(valueToAdd: oneWaiter);
269 }
270 return false;
271}
272
273class QSemaphorePrivate {
274public:
275 inline QSemaphorePrivate(int n) : avail(n) { }
276
277 QMutex mutex;
278 QWaitCondition cond;
279
280 int avail;
281};
282
283/*!
284 Creates a new semaphore and initializes the number of resources
285 it guards to \a n (by default, 0).
286
287 \sa release(), available()
288*/
289QSemaphore::QSemaphore(int n)
290{
291 Q_ASSERT_X(n >= 0, "QSemaphore", "parameter 'n' must be non-negative");
292 if (futexAvailable()) {
293 quintptr nn = unsigned(n);
294 if (futexHasWaiterCount)
295 nn |= quint64(nn) << 32; // token count replicated in high word
296 u.storeRelaxed(newValue: nn);
297 } else {
298 d = new QSemaphorePrivate(n);
299 }
300}
301
302/*!
303 Destroys the semaphore.
304
305 \warning Destroying a semaphore that is in use may result in
306 undefined behavior.
307*/
308QSemaphore::~QSemaphore()
309{
310 if (!futexAvailable())
311 delete d;
312}
313
314/*!
315 Tries to acquire \c n resources guarded by the semaphore. If \a n
316 > available(), this call will block until enough resources are
317 available.
318
319 \sa release(), available(), tryAcquire()
320*/
321void QSemaphore::acquire(int n)
322{
323 Q_ASSERT_X(n >= 0, "QSemaphore::acquire", "parameter 'n' must be non-negative");
324
325 if (futexAvailable()) {
326 futexSemaphoreTryAcquire<false>(u&: u, n, timeout: -1);
327 return;
328 }
329
330 QMutexLocker locker(&d->mutex);
331 while (n > d->avail)
332 d->cond.wait(lockedMutex: locker.mutex());
333 d->avail -= n;
334}
335
336/*!
337 Releases \a n resources guarded by the semaphore.
338
339 This function can be used to "create" resources as well. For
340 example:
341
342 \snippet code/src_corelib_thread_qsemaphore.cpp 1
343
344 QSemaphoreReleaser is a \l{http://en.cppreference.com/w/cpp/language/raii}{RAII}
345 wrapper around this function.
346
347 \sa acquire(), available(), QSemaphoreReleaser
348*/
349void QSemaphore::release(int n)
350{
351 Q_ASSERT_X(n >= 0, "QSemaphore::release", "parameter 'n' must be non-negative");
352
353 if (futexAvailable()) {
354 quintptr nn = unsigned(n);
355 if (futexHasWaiterCount)
356 nn |= quint64(nn) << 32; // token count replicated in high word
357 quintptr prevValue = u.fetchAndAddRelease(valueToAdd: nn);
358 if (futexNeedsWake(v: prevValue)) {
359#ifdef FUTEX_OP
360 if (futexHasWaiterCount) {
361 /*
362 On 64-bit systems, the single-token waiters wait on the low half
363 and the multi-token waiters wait on the upper half. So we ask
364 the kernel to wake up n single-token waiters and all multi-token
365 waiters (if any), and clear the multi-token wait bit.
366
367 atomic {
368 int oldval = *upper;
369 *upper = oldval | 0;
370 futexWake(lower, n);
371 if (oldval != 0) // always true
372 futexWake(upper, INT_MAX);
373 }
374 */
375 quint32 op = FUTEX_OP_OR;
376 quint32 oparg = 0;
377 quint32 cmp = FUTEX_OP_CMP_NE;
378 quint32 cmparg = 0;
379 u.fetchAndAndRelease(valueToAdd: futexNeedsWakeAllBit - 1);
380 futexWakeOp(futex1&: *futexLow32(ptr: &u), wake1: n, INT_MAX, futex2&: *futexHigh32(ptr: &u), FUTEX_OP(op, oparg, cmp, cmparg));
381 return;
382 }
383#endif
384 // Unset the bit and wake everyone. There are two possibilities
385 // under which a thread can set the bit between the AND and the
386 // futexWake:
387 // 1) it did see the new counter value, but it wasn't enough for
388 // its acquisition anyway, so it has to wait;
389 // 2) it did not see the new counter value, in which case its
390 // futexWait will fail.
391 u.fetchAndAndRelease(valueToAdd: futexNeedsWakeAllBit - 1);
392 if (futexHasWaiterCount) {
393 futexWakeAll(futex&: *futexLow32(ptr: &u));
394 futexWakeAll(futex&: *futexHigh32(ptr: &u));
395 } else {
396 futexWakeAll(futex&: u);
397 }
398 }
399 return;
400 }
401
402 QMutexLocker locker(&d->mutex);
403 d->avail += n;
404 d->cond.wakeAll();
405}
406
407/*!
408 Returns the number of resources currently available to the
409 semaphore. This number can never be negative.
410
411 \sa acquire(), release()
412*/
413int QSemaphore::available() const
414{
415 if (futexAvailable())
416 return futexAvailCounter(v: u.loadRelaxed());
417
418 QMutexLocker locker(&d->mutex);
419 return d->avail;
420}
421
422/*!
423 Tries to acquire \c n resources guarded by the semaphore and
424 returns \c true on success. If available() < \a n, this call
425 immediately returns \c false without acquiring any resources.
426
427 Example:
428
429 \snippet code/src_corelib_thread_qsemaphore.cpp 2
430
431 \sa acquire()
432*/
433bool QSemaphore::tryAcquire(int n)
434{
435 Q_ASSERT_X(n >= 0, "QSemaphore::tryAcquire", "parameter 'n' must be non-negative");
436
437 if (futexAvailable())
438 return futexSemaphoreTryAcquire<false>(u&: u, n, timeout: 0);
439
440 QMutexLocker locker(&d->mutex);
441 if (n > d->avail)
442 return false;
443 d->avail -= n;
444 return true;
445}
446
447/*!
448 Tries to acquire \c n resources guarded by the semaphore and
449 returns \c true on success. If available() < \a n, this call will
450 wait for at most \a timeout milliseconds for resources to become
451 available.
452
453 Note: Passing a negative number as the \a timeout is equivalent to
454 calling acquire(), i.e. this function will wait forever for
455 resources to become available if \a timeout is negative.
456
457 Example:
458
459 \snippet code/src_corelib_thread_qsemaphore.cpp 3
460
461 \sa acquire()
462*/
463bool QSemaphore::tryAcquire(int n, int timeout)
464{
465 Q_ASSERT_X(n >= 0, "QSemaphore::tryAcquire", "parameter 'n' must be non-negative");
466
467 // We're documented to accept any negative value as "forever"
468 // but QDeadlineTimer only accepts -1.
469 timeout = qMax(a: timeout, b: -1);
470
471 if (futexAvailable())
472 return futexSemaphoreTryAcquire<true>(u&: u, n, timeout);
473
474 QDeadlineTimer timer(timeout);
475 QMutexLocker locker(&d->mutex);
476 while (n > d->avail && !timer.hasExpired()) {
477 if (!d->cond.wait(lockedMutex: locker.mutex(), deadline: timer))
478 return false;
479 }
480 if (n > d->avail)
481 return false;
482 d->avail -= n;
483 return true;
484
485
486}
487
488/*!
489 \class QSemaphoreReleaser
490 \brief The QSemaphoreReleaser class provides exception-safe deferral of a QSemaphore::release() call.
491 \since 5.10
492 \ingroup thread
493 \inmodule QtCore
494
495 \reentrant
496
497 QSemaphoreReleaser can be used wherever you would otherwise use
498 QSemaphore::release(). Constructing a QSemaphoreReleaser defers the
499 release() call on the semaphore until the QSemaphoreReleaser is
500 destroyed (see
501 \l{http://en.cppreference.com/w/cpp/language/raii}{RAII pattern}).
502
503 You can use this to reliably release a semaphore to avoid dead-lock
504 in the face of exceptions or early returns:
505
506 \snippet code/src_corelib_thread_qsemaphore.cpp 4
507
508 If an early return is taken or an exception is thrown before the
509 \c{sem.release()} call is reached, the semaphore is not released,
510 possibly preventing the thread waiting in the corresponding
511 \c{sem.acquire()} call from ever continuing execution.
512
513 When using RAII instead:
514
515 \snippet code/src_corelib_thread_qsemaphore.cpp 5
516
517 this can no longer happen, because the compiler will make sure that
518 the QSemaphoreReleaser destructor is always called, and therefore
519 the semaphore is always released.
520
521 QSemaphoreReleaser is move-enabled and can therefore be returned
522 from functions to transfer responsibility for releasing a semaphore
523 out of a function or a scope:
524
525 \snippet code/src_corelib_thread_qsemaphore.cpp 6
526
527 A QSemaphoreReleaser can be canceled by a call to cancel(). A canceled
528 semaphore releaser will no longer call QSemaphore::release() in its
529 destructor.
530
531 \sa QMutexLocker
532*/
533
534/*!
535 \fn QSemaphoreReleaser::QSemaphoreReleaser()
536
537 Default constructor. Creates a QSemaphoreReleaser that does nothing.
538*/
539
540/*!
541 \fn QSemaphoreReleaser::QSemaphoreReleaser(QSemaphore &sem, int n)
542
543 Constructor. Stores the arguments and calls \a{sem}.release(\a{n})
544 in the destructor.
545*/
546
547/*!
548 \fn QSemaphoreReleaser::QSemaphoreReleaser(QSemaphore *sem, int n)
549
550 Constructor. Stores the arguments and calls \a{sem}->release(\a{n})
551 in the destructor.
552*/
553
554/*!
555 \fn QSemaphoreReleaser::QSemaphoreReleaser(QSemaphoreReleaser &&other)
556
557 Move constructor. Takes over responsibility to call QSemaphore::release()
558 from \a other, which in turn is canceled.
559
560 \sa cancel()
561*/
562
563/*!
564 \fn QSemaphoreReleaser::operator=(QSemaphoreReleaser &&other)
565
566 Move assignment operator. Takes over responsibility to call QSemaphore::release()
567 from \a other, which in turn is canceled.
568
569 If this semaphore releaser had the responsibility to call some QSemaphore::release()
570 itself, it performs the call before taking over from \a other.
571
572 \sa cancel()
573*/
574
575/*!
576 \fn QSemaphoreReleaser::~QSemaphoreReleaser()
577
578 Unless canceled, calls QSemaphore::release() with the arguments provided
579 to the constructor, or by the last move assignment.
580*/
581
582/*!
583 \fn QSemaphoreReleaser::swap(QSemaphoreReleaser &other)
584
585 Exchanges the responsibilites of \c{*this} and \a other.
586
587 Unlike move assignment, neither of the two objects ever releases its
588 semaphore, if any, as a consequence of swapping.
589
590 Therefore this function is very fast and never fails.
591*/
592
593/*!
594 \fn QSemaphoreReleaser::semaphore() const
595
596 Returns a pointer to the QSemaphore object provided to the constructor,
597 or by the last move assignment, if any. Otherwise, returns \nullptr.
598*/
599
600/*!
601 \fn QSemaphoreReleaser::cancel()
602
603 Cancels this QSemaphoreReleaser such that the destructor will no longer
604 call \c{semaphore()->release()}. Returns the value of semaphore()
605 before this call. After this call, semaphore() will return \nullptr.
606
607 To enable again, assign a new QSemaphoreReleaser:
608
609 \snippet code/src_corelib_thread_qsemaphore.cpp 7
610*/
611
612
613QT_END_NAMESPACE
614

source code of qtbase/src/corelib/thread/qsemaphore.cpp