From b8f639f27a05043f9f9ac371352508d6527f0123 Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Fri, 10 Dec 2010 10:00:54 +0100 Subject: Comment a bit more the timer ID allocation code. Also add the notes for where to place .loadAcquire when that function exists. Reviewed-By: Bradley T. Hughes --- src/corelib/kernel/qabstracteventdispatcher.cpp | 24 ++++++++++++++++++++++-- 1 file changed, 22 insertions(+), 2 deletions(-) diff --git a/src/corelib/kernel/qabstracteventdispatcher.cpp b/src/corelib/kernel/qabstracteventdispatcher.cpp index bcf4477..1c1c6e3 100644 --- a/src/corelib/kernel/qabstracteventdispatcher.cpp +++ b/src/corelib/kernel/qabstracteventdispatcher.cpp @@ -120,11 +120,20 @@ void QAbstractEventDispatcherPrivate::init() } } +// Timer IDs are implemented using a free-list; +// there's a vector initialized with: +// X[i] = i + 1 +// and nextFreeTimerId starts with 1. +// +// Allocating a timer ID involves taking the ID from +// X[nextFreeTimerId] +// updating nextFreeTimerId to this value and returning the old value +// (continues below). int QAbstractEventDispatcherPrivate::allocateTimerId() { int timerId, newTimerId; do { - timerId = nextFreeTimerId; + timerId = nextFreeTimerId; //.loadAcquire(); // ### FIXME Proper memory ordering semantics // which bucket are we looking in? int which = timerId & 0x00ffffff; @@ -148,6 +157,17 @@ int QAbstractEventDispatcherPrivate::allocateTimerId() return timerId; } +// Releasing a timer ID requires putting the current ID back in the vector; +// we do it by setting: +// X[timerId] = nextFreeTimerId; +// then we update nextFreeTimerId to the timer we've just released +// +// The extra code in allocateTimerId and releaseTimerId are ABA prevention +// and bucket memory. The buckets are simply to make sure we allocate only +// the necessary number of timers. See above. +// +// ABA prevention simply adds a value to 7 of the top 8 bits when resetting +// nextFreeTimerId. void QAbstractEventDispatcherPrivate::releaseTimerId(int timerId) { int which = timerId & 0x00ffffff; @@ -157,7 +177,7 @@ void QAbstractEventDispatcherPrivate::releaseTimerId(int timerId) int freeId, newTimerId; do { - freeId = nextFreeTimerId; + freeId = nextFreeTimerId;//.loadAcquire(); // ### FIXME Proper memory ordering semantics b[at] = freeId & 0x00ffffff; newTimerId = prepareNewValueWithSerialNumber(freeId, timerId); -- cgit v0.12 From f0a892a46fdc438277c8b401c267db4bd92aec1b Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Mon, 13 Dec 2010 14:50:07 +0100 Subject: Fix ABA problem with: the serial must be updated on all accesses The nextFreeTimerId's serial counter was only being updated on timer ID releasing. It needs to be updated on allocation too. Reviewed-by: Bradley T. Hughes --- src/corelib/kernel/qabstracteventdispatcher.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/corelib/kernel/qabstracteventdispatcher.cpp b/src/corelib/kernel/qabstracteventdispatcher.cpp index 1c1c6e3..5619921 100644 --- a/src/corelib/kernel/qabstracteventdispatcher.cpp +++ b/src/corelib/kernel/qabstracteventdispatcher.cpp @@ -151,7 +151,7 @@ int QAbstractEventDispatcherPrivate::allocateTimerId() } } - newTimerId = b[at]; + newTimerId = prepareNewValueWithSerialNumber(timerId, b[at]); } while (!nextFreeTimerId.testAndSetRelaxed(timerId, newTimerId)); return timerId; -- cgit v0.12 From a02a747a9d5294127dfe3e676a2759e228257e70 Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Mon, 13 Dec 2010 14:58:16 +0100 Subject: Use constants the timer ID masks instead of values everywhere Reviewed-By: Bradley T. Hughes --- src/corelib/kernel/qabstracteventdispatcher.cpp | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/src/corelib/kernel/qabstracteventdispatcher.cpp b/src/corelib/kernel/qabstracteventdispatcher.cpp index 5619921..002d360 100644 --- a/src/corelib/kernel/qabstracteventdispatcher.cpp +++ b/src/corelib/kernel/qabstracteventdispatcher.cpp @@ -77,10 +77,14 @@ Q_DESTRUCTOR_FUNCTION(timerIdsDestructorFunction) static QBasicAtomicInt nextFreeTimerId = Q_BASIC_ATOMIC_INITIALIZER(1); +static const int TimerIdMask = 0x00ffffff; +static const int TimerSerialMask = ~TimerIdMask & ~0x80000000; +static const int TimerSerialCounter = TimerIdMask + 1; + // avoid the ABA-problem by using 7 of the top 8 bits of the timerId as a serial number static inline int prepareNewValueWithSerialNumber(int oldId, int newId) { - return (newId & 0x00FFFFFF) | ((oldId + 0x01000000) & 0x7f000000); + return (newId & TimerIdMask) | ((oldId + TimerSerialCounter) & TimerSerialMask); } static inline int bucketOffset(int timerId) @@ -136,7 +140,7 @@ int QAbstractEventDispatcherPrivate::allocateTimerId() timerId = nextFreeTimerId; //.loadAcquire(); // ### FIXME Proper memory ordering semantics // which bucket are we looking in? - int which = timerId & 0x00ffffff; + int which = timerId & TimerIdMask; int bucket = bucketOffset(which); int at = bucketIndex(bucket, which); int *b = timerIds[bucket]; @@ -170,7 +174,7 @@ int QAbstractEventDispatcherPrivate::allocateTimerId() // nextFreeTimerId. void QAbstractEventDispatcherPrivate::releaseTimerId(int timerId) { - int which = timerId & 0x00ffffff; + int which = timerId & TimerIdMask; int bucket = bucketOffset(which); int at = bucketIndex(bucket, which); int *b = timerIds[bucket]; @@ -178,7 +182,7 @@ void QAbstractEventDispatcherPrivate::releaseTimerId(int timerId) int freeId, newTimerId; do { freeId = nextFreeTimerId;//.loadAcquire(); // ### FIXME Proper memory ordering semantics - b[at] = freeId & 0x00ffffff; + b[at] = freeId & TimerIdMask; newTimerId = prepareNewValueWithSerialNumber(freeId, timerId); } while (!nextFreeTimerId.testAndSetRelease(freeId, newTimerId)); -- cgit v0.12 From bd9d5c80235ce6d1b005df96c3058b75e82bd6f0 Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Mon, 13 Dec 2010 15:02:27 +0100 Subject: Add a small protection against releasing a timer twice. The cell corresponding to an allocated timer ID in the free list is unused (because the ID isn't free). So use it to store an invalid value that we can check against the user's value. This provides some protection against a given timer being released twice. Since we store the serial counter of the nextFreeTimerId, getting the same ID twice is a 1-in-128 chance. Reviewed-By: Bradley T. Hughes --- src/corelib/kernel/qabstracteventdispatcher.cpp | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) diff --git a/src/corelib/kernel/qabstracteventdispatcher.cpp b/src/corelib/kernel/qabstracteventdispatcher.cpp index 002d360..bf675a7 100644 --- a/src/corelib/kernel/qabstracteventdispatcher.cpp +++ b/src/corelib/kernel/qabstracteventdispatcher.cpp @@ -132,18 +132,24 @@ void QAbstractEventDispatcherPrivate::init() // Allocating a timer ID involves taking the ID from // X[nextFreeTimerId] // updating nextFreeTimerId to this value and returning the old value +// +// When the timer ID is allocated, its cell in the vector is unused (it's a +// free list). As an added protection, we use the cell to store an invalid +// (negative) value that we can later check for integrity. +// // (continues below). int QAbstractEventDispatcherPrivate::allocateTimerId() { int timerId, newTimerId; + int at, *b; do { timerId = nextFreeTimerId; //.loadAcquire(); // ### FIXME Proper memory ordering semantics // which bucket are we looking in? int which = timerId & TimerIdMask; int bucket = bucketOffset(which); - int at = bucketIndex(bucket, which); - int *b = timerIds[bucket]; + at = bucketIndex(bucket, which); + b = timerIds[bucket]; if (!b) { // allocate a new bucket @@ -158,6 +164,8 @@ int QAbstractEventDispatcherPrivate::allocateTimerId() newTimerId = prepareNewValueWithSerialNumber(timerId, b[at]); } while (!nextFreeTimerId.testAndSetRelaxed(timerId, newTimerId)); + b[at] = -timerId; + return timerId; } @@ -179,6 +187,8 @@ void QAbstractEventDispatcherPrivate::releaseTimerId(int timerId) int at = bucketIndex(bucket, which); int *b = timerIds[bucket]; + Q_ASSERT(b[at] == -timerId); + int freeId, newTimerId; do { freeId = nextFreeTimerId;//.loadAcquire(); // ### FIXME Proper memory ordering semantics -- cgit v0.12