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 constexpr bool futexHasWaiterCount = true;
131#else
132static 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(curValue) >= n) {
190 // try to acquire
191 quintptr newValue = curValue - nn;
192 if (u.testAndSetOrdered(curValue, newValue, 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(&u);
204 if (n > 1 || !futexHasWaiterCount) {
205 u.fetchAndOrRelaxed(futexNeedsWakeAllBit);
206 curValue |= futexNeedsWakeAllBit;
207 if (n > 1 && futexHasWaiterCount) {
208 ptr = futexHigh32(&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(*ptr, curValue, remainingTime);
216 if (timedout)
217 return false;
218 } else {
219 futexWait(*ptr, 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(curValue) >= n) {
238 // try to acquire
239 quintptr newValue = curValue - nn;
240 if (u.testAndSetOrdered(curValue, newValue, 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(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(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(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, n, -1);
327 return;
328 }
329
330 QMutexLocker locker(&d->mutex);
331 while (n > d->avail)
332 d->cond.wait(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(nn);
358 if (futexNeedsWake(prevValue)) {
359#ifdef FUTEX_OP
360 if (!futexHasWaiterCount) {
361 /*
362 On 32-bit systems, all waiters are waiting on the same address,
363 so we'll wake them all and ask the kernel to clear the high bit.
364
365 atomic {
366 int oldval = u;
367 u = oldval & ~(1 << 31);
368 futexWake(u, INT_MAX);
369 if (oldval == 0) // impossible condition
370 futexWake(u, INT_MAX);
371 }
372 */
373 quint32 op = FUTEX_OP_ANDN | FUTEX_OP_OPARG_SHIFT;
374 quint32 oparg = 31;
375 quint32 cmp = FUTEX_OP_CMP_EQ;
376 quint32 cmparg = 0;
377 futexWakeOp(u, INT_MAX, INT_MAX, u, FUTEX_OP(op, oparg, cmp, cmparg));
378 } else {
379 /*
380 On 64-bit systems, the single-token waiters wait on the low half
381 and the multi-token waiters wait on the upper half. So we ask
382 the kernel to wake up n single-token waiters and all multi-token
383 waiters (if any), then clear the multi-token wait bit.
384
385 atomic {
386 int oldval = *upper;
387 *upper = oldval & ~(1 << 31);
388 futexWake(lower, n);
389 if (oldval < 0) // sign bit set
390 futexWake(upper, INT_MAX);
391 }
392 */
393 quint32 op = FUTEX_OP_ANDN | FUTEX_OP_OPARG_SHIFT;
394 quint32 oparg = 31;
395 quint32 cmp = FUTEX_OP_CMP_LT;
396 quint32 cmparg = 0;
397 futexWakeOp(*futexLow32(&u), n, INT_MAX, *futexHigh32(&u), FUTEX_OP(op, oparg, cmp, cmparg));
398 }
399#else
400 // Unset the bit and wake everyone. There are two possibibilies
401 // under which a thread can set the bit between the AND and the
402 // futexWake:
403 // 1) it did see the new counter value, but it wasn't enough for
404 // its acquisition anyway, so it has to wait;
405 // 2) it did not see the new counter value, in which case its
406 // futexWait will fail.
407 u.fetchAndAndRelease(futexNeedsWakeAllBit - 1);
408 futexWakeAll(u);
409#endif
410 }
411 return;
412 }
413
414 QMutexLocker locker(&d->mutex);
415 d->avail += n;
416 d->cond.wakeAll();
417}
418
419/*!
420 Returns the number of resources currently available to the
421 semaphore. This number can never be negative.
422
423 \sa acquire(), release()
424*/
425int QSemaphore::available() const
426{
427 if (futexAvailable())
428 return futexAvailCounter(u.loadRelaxed());
429
430 QMutexLocker locker(&d->mutex);
431 return d->avail;
432}
433
434/*!
435 Tries to acquire \c n resources guarded by the semaphore and
436 returns \c true on success. If available() < \a n, this call
437 immediately returns \c false without acquiring any resources.
438
439 Example:
440
441 \snippet code/src_corelib_thread_qsemaphore.cpp 2
442
443 \sa acquire()
444*/
445bool QSemaphore::tryAcquire(int n)
446{
447 Q_ASSERT_X(n >= 0, "QSemaphore::tryAcquire", "parameter 'n' must be non-negative");
448
449 if (futexAvailable())
450 return futexSemaphoreTryAcquire<false>(u, n, 0);
451
452 QMutexLocker locker(&d->mutex);
453 if (n > d->avail)
454 return false;
455 d->avail -= n;
456 return true;
457}
458
459/*!
460 Tries to acquire \c n resources guarded by the semaphore and
461 returns \c true on success. If available() < \a n, this call will
462 wait for at most \a timeout milliseconds for resources to become
463 available.
464
465 Note: Passing a negative number as the \a timeout is equivalent to
466 calling acquire(), i.e. this function will wait forever for
467 resources to become available if \a timeout is negative.
468
469 Example:
470
471 \snippet code/src_corelib_thread_qsemaphore.cpp 3
472
473 \sa acquire()
474*/
475bool QSemaphore::tryAcquire(int n, int timeout)
476{
477 Q_ASSERT_X(n >= 0, "QSemaphore::tryAcquire", "parameter 'n' must be non-negative");
478
479 // We're documented to accept any negative value as "forever"
480 // but QDeadlineTimer only accepts -1.
481 timeout = qMax(timeout, -1);
482
483 if (futexAvailable())
484 return futexSemaphoreTryAcquire<true>(u, n, timeout);
485
486 QDeadlineTimer timer(timeout);
487 QMutexLocker locker(&d->mutex);
488 while (n > d->avail && !timer.hasExpired()) {
489 if (!d->cond.wait(locker.mutex(), timer))
490 return false;
491 }
492 if (n > d->avail)
493 return false;
494 d->avail -= n;
495 return true;
496
497
498}
499
500/*!
501 \class QSemaphoreReleaser
502 \brief The QSemaphoreReleaser class provides exception-safe deferral of a QSemaphore::release() call.
503 \since 5.10
504 \ingroup thread
505 \inmodule QtCore
506
507 \reentrant
508
509 QSemaphoreReleaser can be used wherever you would otherwise use
510 QSemaphore::release(). Constructing a QSemaphoreReleaser defers the
511 release() call on the semaphore until the QSemaphoreReleaser is
512 destroyed (see
513 \l{http://en.cppreference.com/w/cpp/language/raii}{RAII pattern}).
514
515 You can use this to reliably release a semaphore to avoid dead-lock
516 in the face of exceptions or early returns:
517
518 \snippet code/src_corelib_thread_qsemaphore.cpp 4
519
520 If an early return is taken or an exception is thrown before the
521 \c{sem.release()} call is reached, the semaphore is not released,
522 possibly preventing the thread waiting in the corresponding
523 \c{sem.acquire()} call from ever continuing execution.
524
525 When using RAII instead:
526
527 \snippet code/src_corelib_thread_qsemaphore.cpp 5
528
529 this can no longer happen, because the compiler will make sure that
530 the QSemaphoreReleaser destructor is always called, and therefore
531 the semaphore is always released.
532
533 QSemaphoreReleaser is move-enabled and can therefore be returned
534 from functions to transfer responsibility for releasing a semaphore
535 out of a function or a scope:
536
537 \snippet code/src_corelib_thread_qsemaphore.cpp 6
538
539 A QSemaphoreReleaser can be canceled by a call to cancel(). A canceled
540 semaphore releaser will no longer call QSemaphore::release() in its
541 destructor.
542
543 \sa QMutexLocker
544*/
545
546/*!
547 \fn QSemaphoreReleaser::QSemaphoreReleaser()
548
549 Default constructor. Creates a QSemaphoreReleaser that does nothing.
550*/
551
552/*!
553 \fn QSemaphoreReleaser::QSemaphoreReleaser(QSemaphore &sem, int n)
554
555 Constructor. Stores the arguments and calls \a{sem}.release(\a{n})
556 in the destructor.
557*/
558
559/*!
560 \fn QSemaphoreReleaser::QSemaphoreReleaser(QSemaphore *sem, int n)
561
562 Constructor. Stores the arguments and calls \a{sem}->release(\a{n})
563 in the destructor.
564*/
565
566/*!
567 \fn QSemaphoreReleaser::QSemaphoreReleaser(QSemaphoreReleaser &&other)
568
569 Move constructor. Takes over responsibility to call QSemaphore::release()
570 from \a other, which in turn is canceled.
571
572 \sa cancel()
573*/
574
575/*!
576 \fn QSemaphoreReleaser::operator=(QSemaphoreReleaser &&other)
577
578 Move assignment operator. Takes over responsibility to call QSemaphore::release()
579 from \a other, which in turn is canceled.
580
581 If this semaphore releaser had the responsibility to call some QSemaphore::release()
582 itself, it performs the call before taking over from \a other.
583
584 \sa cancel()
585*/
586
587/*!
588 \fn QSemaphoreReleaser::~QSemaphoreReleaser()
589
590 Unless canceled, calls QSemaphore::release() with the arguments provided
591 to the constructor, or by the last move assignment.
592*/
593
594/*!
595 \fn QSemaphoreReleaser::swap(QSemaphoreReleaser &other)
596
597 Exchanges the responsibilites of \c{*this} and \a other.
598
599 Unlike move assignment, neither of the two objects ever releases its
600 semaphore, if any, as a consequence of swapping.
601
602 Therefore this function is very fast and never fails.
603*/
604
605/*!
606 \fn QSemaphoreReleaser::semaphore() const
607
608 Returns a pointer to the QSemaphore object provided to the constructor,
609 or by the last move assignment, if any. Otherwise, returns \nullptr.
610*/
611
612/*!
613 \fn QSemaphoreReleaser::cancel()
614
615 Cancels this QSemaphoreReleaser such that the destructor will no longer
616 call \c{semaphore()->release()}. Returns the value of semaphore()
617 before this call. After this call, semaphore() will return \nullptr.
618
619 To enable again, assign a new QSemaphoreReleaser:
620
621 \snippet code/src_corelib_thread_qsemaphore.cpp 7
622*/
623
624
625QT_END_NAMESPACE
626