From e83bb2fdfc2dc899526c8157fd8b77a68cdde9da Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Thu, 22 Oct 2009 21:09:24 +0200 Subject: Fix Qt containers to properly support types with strict alignments. QContiguousCache is a new type, so there are no binary compatibility issues. QHash and QMap didn't have any public qMalloc / qFree, so the entire logic is contained in .cpp code. However, since old code will not inform us of the alignment requirements, we need to add a bit to the structure to indicate whether strict alignment is in use or not. QList doesn't require any changes. For small, movable types, they're all stored in the pointer array itself, so they're aligned. For larger types, we use new(), so types with stricter requirements should define their own operator new(). QLinkedList cannot be fixed. It uses new() on the QLinkedListNode, which contains a T type. Sorry. QVector did have public qMalloc / qFree. I've moved the calls to the inner function and made it keep the old calls if the alignment requirement is below a certain threshold. The idea is that, if it's above, no one was using QVector anyway. Reviewed-by: Bradley T. Hughes --- src/corelib/global/qmalloc.cpp | 3 - src/corelib/tools/qcontiguouscache.cpp | 10 +++ src/corelib/tools/qcontiguouscache.h | 15 +++- src/corelib/tools/qhash.cpp | 27 ++++--- src/corelib/tools/qhash.h | 36 ++++++---- src/corelib/tools/qmap.cpp | 31 ++++++-- src/corelib/tools/qmap.h | 20 ++++-- src/corelib/tools/qvector.cpp | 27 +++++++ src/corelib/tools/qvector.h | 20 +++++- tests/auto/collections/tst_collections.cpp | 109 +++++++++++++++++++++++++++++ 10 files changed, 259 insertions(+), 39 deletions(-) diff --git a/src/corelib/global/qmalloc.cpp b/src/corelib/global/qmalloc.cpp index db5e519..e33f77c 100644 --- a/src/corelib/global/qmalloc.cpp +++ b/src/corelib/global/qmalloc.cpp @@ -144,9 +144,6 @@ void *qReallocAligned(void *oldptr, size_t newsize, size_t oldsize, size_t align // faked-sizeof(void*) is properly aligned for a pointer faked.pptr[-1] = real.ptr; - // and save the actual size just before the pointer - //reinterpret_cast(faked.pptr - 1)[-1] = size; - return faked.ptr; #endif } diff --git a/src/corelib/tools/qcontiguouscache.cpp b/src/corelib/tools/qcontiguouscache.cpp index b0ed701..dd7cab6 100644 --- a/src/corelib/tools/qcontiguouscache.cpp +++ b/src/corelib/tools/qcontiguouscache.cpp @@ -56,6 +56,16 @@ void QContiguousCacheData::dump() const } #endif +QContiguousCacheData *QContiguousCacheData::allocate(int size, int alignment) +{ + return static_cast(qMallocAligned(size, alignment)); +} + +void QContiguousCacheData::free(QContiguousCacheData *data) +{ + qFreeAligned(data); +} + /*! \class QContiguousCache \brief The QContiguousCache class is a template class that provides a contiguous cache. \ingroup tools diff --git a/src/corelib/tools/qcontiguouscache.h b/src/corelib/tools/qcontiguouscache.h index 862df61..b9d04b8 100644 --- a/src/corelib/tools/qcontiguouscache.h +++ b/src/corelib/tools/qcontiguouscache.h @@ -69,6 +69,9 @@ struct Q_CORE_EXPORT QContiguousCacheData // there will be an 8 byte gap here if T requires 16-byte alignment // (such as long double on 64-bit platforms, __int128, __float128) + static QContiguousCacheData *allocate(int size, int alignment); + static void free(QContiguousCacheData *data); + #ifdef QT_QCONTIGUOUSCACHE_DEBUG void dump() const; #endif @@ -161,6 +164,14 @@ private: // count the padding at the end return reinterpret_cast(&(reinterpret_cast(this))->array[1]) - reinterpret_cast(this); } + int alignOfTypedData() const + { +#ifdef Q_ALIGNOF + return qMax(sizeof(void*), Q_ALIGNOF(Data)); +#else + return 0; +#endif + } }; template @@ -262,7 +273,7 @@ void QContiguousCache::clear() template inline QContiguousCacheData *QContiguousCache::malloc(int aalloc) { - return static_cast(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T))); + return QContiguousCacheData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData()); } template @@ -317,7 +328,7 @@ void QContiguousCache::free(Data *x) i = p->array; } } - qFree(x); + x->free(x); } template void QContiguousCache::append(const T &value) diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp index f33aba9..23fff1c 100644 --- a/src/corelib/tools/qhash.cpp +++ b/src/corelib/tools/qhash.cpp @@ -166,29 +166,38 @@ static int countBits(int hint) const int MinNumBits = 4; QHashData QHashData::shared_null = { - 0, 0, Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, MinNumBits, 0, 0, true + 0, 0, Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, MinNumBits, 0, 0, true, false }; void *QHashData::allocateNode() { - void *ptr = qMalloc(nodeSize); + return allocateNode(0); +} + +void *QHashData::allocateNode(int nodeAlign) +{ + void *ptr = strictAlignment ? qMallocAligned(nodeSize, nodeAlign) : qMalloc(nodeSize); Q_CHECK_PTR(ptr); return ptr; } void QHashData::freeNode(void *node) { - qFree(node); + if (strictAlignment) + qFreeAligned(node); + else + qFree(node); } QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize) { - return detach_helper( node_duplicate, 0, nodeSize ); + return detach_helper2( node_duplicate, 0, nodeSize, 0 ); } -QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), - void (*node_delete)(Node *), - int nodeSize) +QHashData *QHashData::detach_helper2(void (*node_duplicate)(Node *, void *), + void (*node_delete)(Node *), + int nodeSize, + int nodeAlign) { union { QHashData *d; @@ -204,6 +213,7 @@ QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), d->numBits = numBits; d->numBuckets = numBuckets; d->sharable = true; + d->strictAlignment = nodeAlign > 8; if (numBuckets) { QT_TRY { @@ -222,7 +232,7 @@ QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), Node *oldNode = buckets[i]; while (oldNode != this_e) { QT_TRY { - Node *dup = static_cast(allocateNode()); + Node *dup = static_cast(allocateNode(nodeAlign)); QT_TRY { node_duplicate(oldNode, dup); @@ -262,6 +272,7 @@ void QHashData::free_helper(void (*node_delete)(Node *)) while (cur != this_e) { Node *next = cur->next; node_delete(cur); + freeNode(cur); cur = next; } } diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index b65f1d3..67b394b 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -125,12 +125,14 @@ struct Q_CORE_EXPORT QHashData short numBits; int numBuckets; uint sharable : 1; + uint strictAlignment : 1; - void *allocateNode(); + void *allocateNode(); // ### Qt5 remove me + void *allocateNode(int nodeAlign); void freeNode(void *node); QHashData *detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize); // ### Qt5 remove me - QHashData *detach_helper(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *), - int nodeSize); + QHashData *detach_helper2(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *), + int nodeSize, int nodeAlign); void mightGrow(); bool willGrow(); void hasShrunk(); @@ -267,6 +269,14 @@ class QHash return reinterpret_cast(node); } +#ifdef Q_ALIGNOF + static inline int alignOfNode() { return qMax(sizeof(void*), Q_ALIGNOF(Node)); } + static inline int alignOfDummyNode() { return qMax(sizeof(void*), Q_ALIGNOF(DummyNode)); } +#else + static inline int alignOfNode() { return 0; } + static inline int alignOfDummyNode() { return 0; } +#endif + public: inline QHash() : d(&QHashData::shared_null) { d->ref.ref(); } inline QHash(const QHash &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); } @@ -483,7 +493,7 @@ private: Node **findNode(const Key &key, uint *hp = 0) const; Node *createNode(uint h, const Key &key, const T &value, Node **nextNode); void deleteNode(Node *node); - static void deleteNode(QHashData::Node *node); + static void deleteNode2(QHashData::Node *node); static void duplicateNode(QHashData::Node *originalNode, void *newNode); }; @@ -492,12 +502,12 @@ private: template Q_INLINE_TEMPLATE void QHash::deleteNode(Node *node) { - deleteNode(reinterpret_cast(node)); + deleteNode2(reinterpret_cast(node)); + d->freeNode(node); } - template -Q_INLINE_TEMPLATE void QHash::deleteNode(QHashData::Node *node) +Q_INLINE_TEMPLATE void QHash::deleteNode2(QHashData::Node *node) { #ifdef Q_CC_BOR concrete(node)->~QHashNode(); @@ -506,7 +516,6 @@ Q_INLINE_TEMPLATE void QHash::deleteNode(QHashData::Node *node) #else concrete(node)->~Node(); #endif - qFree(node); } template @@ -527,9 +536,9 @@ QHash::createNode(uint ah, const Key &akey, const T &avalue, Node **anex Node *node; if (QTypeInfo::isDummy) { - node = reinterpret_cast(new (d->allocateNode()) DummyNode(akey)); + node = reinterpret_cast(new (d->allocateNode(alignOfDummyNode())) DummyNode(akey)); } else { - node = new (d->allocateNode()) Node(akey, avalue); + node = new (d->allocateNode(alignOfNode())) Node(akey, avalue); } node->h = ah; @@ -554,7 +563,7 @@ Q_INLINE_TEMPLATE QHash &QHash::unite(const QHash &other template Q_OUTOFLINE_TEMPLATE void QHash::freeData(QHashData *x) { - x->free_helper(deleteNode); + x->free_helper(deleteNode2); } template @@ -566,8 +575,9 @@ Q_INLINE_TEMPLATE void QHash::clear() template Q_OUTOFLINE_TEMPLATE void QHash::detach_helper() { - QHashData *x = d->detach_helper(duplicateNode, deleteNode, - QTypeInfo::isDummy ? sizeof(DummyNode) : sizeof(Node)); + QHashData *x = d->detach_helper2(duplicateNode, deleteNode2, + QTypeInfo::isDummy ? sizeof(DummyNode) : sizeof(Node), + QTypeInfo::isDummy ? alignOfDummyNode() : alignOfNode()); if (!d->ref.deref()) freeData(d); d = x; diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp index 1385810..cfb18b4 100644 --- a/src/corelib/tools/qmap.cpp +++ b/src/corelib/tools/qmap.cpp @@ -53,11 +53,16 @@ QT_BEGIN_NAMESPACE QMapData QMapData::shared_null = { &shared_null, { &shared_null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, - Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, false, true + Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, false, true, false }; QMapData *QMapData::createData() { + return createData(0); +} + +QMapData *QMapData::createData(int alignment) +{ QMapData *d = new QMapData; Q_CHECK_PTR(d); Node *e = reinterpret_cast(d); @@ -69,6 +74,7 @@ QMapData *QMapData::createData() d->randomBits = 0; d->insertInOrder = false; d->sharable = true; + d->strictAlignment = alignment > 8; return d; } @@ -80,11 +86,19 @@ void QMapData::continueFreeData(int offset) while (cur != e) { prev = cur; cur = cur->forward[0]; - qFree(reinterpret_cast(prev) - offset); + if (strictAlignment) + qFreeAligned(reinterpret_cast(prev) - offset); + else + qFree(reinterpret_cast(prev) - offset); } delete this; } +QMapData::Node *QMapData::node_create(Node *update[], int offset) +{ + return node_create(update, offset, 0); +} + /*! Creates a new node inside the data structure. @@ -94,10 +108,12 @@ void QMapData::continueFreeData(int offset) \a offset is an amount of bytes that needs to reserved just before the QMapData::Node structure. + \a alignment dictates the alignment for the data. + \internal \since 4.6 */ -QMapData::Node *QMapData::node_create(Node *update[], int offset) +QMapData::Node *QMapData::node_create(Node *update[], int offset, int alignment) { int level = 0; uint mask = (1 << Sparseness) - 1; @@ -118,7 +134,9 @@ QMapData::Node *QMapData::node_create(Node *update[], int offset) if (level == 3 && !insertInOrder) randomBits = qrand(); - void *concreteNode = qMalloc(offset + sizeof(Node) + level * sizeof(Node *)); + void *concreteNode = strictAlignment ? + qMallocAligned(offset + sizeof(Node) + level * sizeof(Node *), alignment) : + qMalloc(offset + sizeof(Node) + level * sizeof(Node *)); Q_CHECK_PTR(concreteNode); Node *abstractNode = reinterpret_cast(reinterpret_cast(concreteNode) + offset); @@ -145,7 +163,10 @@ void QMapData::node_delete(Node *update[], int offset, Node *node) update[i]->forward[i] = node->forward[i]; } --size; - qFree(reinterpret_cast(node) - offset); + if (strictAlignment) + qFreeAligned(reinterpret_cast(node) - offset); + else + qFree(reinterpret_cast(node) - offset); } #ifdef QT_QMAP_DEBUG diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index 688aca6..20980e7 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -74,10 +74,13 @@ struct Q_CORE_EXPORT QMapData uint randomBits; uint insertInOrder : 1; uint sharable : 1; + uint strictAlignment : 1; - static QMapData *createData(); + static QMapData *createData(); // ### Qt5 remove me + static QMapData *createData(int alignment); void continueFreeData(int offset); - Node *node_create(Node *update[], int offset); + Node *node_create(Node *update[], int offset); // ### Qt5 remove me + Node *node_create(Node *update[], int offset, int alignment); void node_delete(Node *update[], int offset, Node *node); #ifdef QT_QMAP_DEBUG uint adjust_ptr(Node *node); @@ -145,6 +148,13 @@ class QMap }; static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); } + static inline int alignment() { +#ifdef Q_ALIGNOF + return qMax(sizeof(void*), Q_ALIGNOF(Node)); +#else + return 0; +#endif + } static inline Node *concrete(QMapData::Node *node) { return reinterpret_cast(reinterpret_cast(node) - payload()); } @@ -414,7 +424,7 @@ template Q_INLINE_TEMPLATE typename QMapData::Node * QMap::node_create(QMapData *adt, QMapData::Node *aupdate[], const Key &akey, const T &avalue) { - QMapData::Node *abstractNode = adt->node_create(aupdate, payload()); + QMapData::Node *abstractNode = adt->node_create(aupdate, payload(), alignment()); QT_TRY { Node *concreteNode = concrete(abstractNode); new (&concreteNode->key) Key(akey); @@ -715,7 +725,7 @@ template Q_OUTOFLINE_TEMPLATE void QMap::detach_helper() { union { QMapData *d; QMapData::Node *e; } x; - x.d = QMapData::createData(); + x.d = QMapData::createData(alignment()); if (d->size) { x.d->insertInOrder = true; QMapData::Node *update[QMapData::LastLevel + 1]; @@ -905,7 +915,7 @@ Q_OUTOFLINE_TEMPLATE bool QMap::operator==(const QMap &other) co template Q_OUTOFLINE_TEMPLATE QMap::QMap(const std::map &other) { - d = QMapData::createData(); + d = QMapData::createData(alignment()); d->insertInOrder = true; typename std::map::const_iterator it = other.end(); while (it != other.begin()) { diff --git a/src/corelib/tools/qvector.cpp b/src/corelib/tools/qvector.cpp index 20f3a80..6522791 100644 --- a/src/corelib/tools/qvector.cpp +++ b/src/corelib/tools/qvector.cpp @@ -45,6 +45,13 @@ QT_BEGIN_NAMESPACE +static inline int alignmentThreshold() +{ + // malloc on 32-bit platforms should return pointers that are 8-byte aligned or more + // while on 64-bit platforms they should be 16-byte aligned or more + return 2 * sizeof(void*); +} + QVectorData QVectorData::shared_null = { Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, true, false }; QVectorData *QVectorData::malloc(int sizeofTypedData, int size, int sizeofT, QVectorData *init) @@ -55,6 +62,26 @@ QVectorData *QVectorData::malloc(int sizeofTypedData, int size, int sizeofT, QVe return p; } +QVectorData *QVectorData::allocate(int size, int alignment) +{ + return static_cast(alignment > alignmentThreshold() ? qMallocAligned(size, alignment) : qMalloc(size)); +} + +QVectorData *QVectorData::reallocate(QVectorData *x, int newsize, int oldsize, int alignment) +{ + if (alignment > alignmentThreshold()) + return static_cast(qReallocAligned(x, newsize, oldsize, alignment)); + return static_cast(qRealloc(x, newsize)); +} + +void QVectorData::free(QVectorData *x, int alignment) +{ + if (alignment > alignmentThreshold()) + qFreeAligned(x); + else + qFree(x); +} + int QVectorData::grow(int sizeofTypedData, int size, int sizeofT, bool excessive) { if (excessive) diff --git a/src/corelib/tools/qvector.h b/src/corelib/tools/qvector.h index b77b53a..cf7df12 100644 --- a/src/corelib/tools/qvector.h +++ b/src/corelib/tools/qvector.h @@ -79,6 +79,9 @@ struct Q_CORE_EXPORT QVectorData // some debugges when the QVector is member of a class within an unnamed namespace. // ### Qt 5: can be removed completely. (Ralf) static QVectorData *malloc(int sizeofTypedData, int size, int sizeofT, QVectorData *init); + static QVectorData *allocate(int size, int alignment); + static QVectorData *reallocate(QVectorData *old, int newsize, int oldsize, int alignment); + static void free(QVectorData *data, int alignment); static int grow(int sizeofTypedData, int size, int sizeofT, bool excessive); }; @@ -87,6 +90,8 @@ struct QVectorTypedData : private QVectorData { // private inheritance as we must not access QVectorData member thought QVectorTypedData // as this would break strict aliasing rules. (in the case of shared_null) T array[1]; + + static inline void free(QVectorTypedData *x, int alignment) { QVectorData::free(x, alignment); } }; class QRegion; @@ -302,6 +307,14 @@ private: // count the padding at the end return reinterpret_cast(&(reinterpret_cast(this))->array[1]) - reinterpret_cast(this); } + inline int alignOfTypedData() const + { +#ifdef Q_ALIGNOF + return qMax(sizeof(void*), Q_ALIGNOF(Data)); +#else + return 0; +#endif + } }; template @@ -373,7 +386,7 @@ QVector &QVector::operator=(const QVector &v) template inline QVectorData *QVector::malloc(int aalloc) { - QVectorData *vectordata = static_cast(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T))); + QVectorData *vectordata = QVectorData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData()); Q_CHECK_PTR(vectordata); return vectordata; } @@ -420,7 +433,7 @@ void QVector::free(Data *x) while (i-- != b) i->~T(); } - qFree(x); + x->free(x, alignOfTypedData()); } template @@ -459,7 +472,8 @@ void QVector::realloc(int asize, int aalloc) } } else { QT_TRY { - QVectorData *mem = static_cast(qRealloc(p, sizeOfTypedData() + (aalloc - 1) * sizeof(T))); + QVectorData *mem = QVectorData::reallocate(d, sizeOfTypedData() + (aalloc - 1) * sizeof(T), + sizeOfTypedData() + (d->alloc - 1) * sizeof(T), alignOfTypedData()); Q_CHECK_PTR(mem); x.d = d = mem; x.d->size = d->size; diff --git a/tests/auto/collections/tst_collections.cpp b/tests/auto/collections/tst_collections.cpp index 670cff0..f97805e 100644 --- a/tests/auto/collections/tst_collections.cpp +++ b/tests/auto/collections/tst_collections.cpp @@ -164,6 +164,7 @@ private slots: void qtimerList(); void containerTypedefs(); void forwardDeclared(); + void alignment(); }; struct LargeStatic { @@ -3481,5 +3482,113 @@ void tst_Collections::forwardDeclared() { typedef QSet C; C *x = 0; /* C::iterator i; */ C::const_iterator j; Q_UNUSED(x) } } +#if defined(Q_ALIGNOF) && defined(Q_DECL_ALIGN) + +class Q_DECL_ALIGN(4) Aligned4 +{ + char i; +public: + Aligned4(int i = 0) : i(i) {} + bool checkAligned() const + { + return (quintptr(this) & 3) == 0; + } + + inline bool operator==(const Aligned4 &other) const { return i == other.i; } + inline bool operator<(const Aligned4 &other) const { return i < other.i; } + friend inline int qHash(const Aligned4 &a) { return qHash(a.i); } +}; + +class Q_DECL_ALIGN(128) Aligned128 +{ + char i; +public: + Aligned128(int i = 0) : i(i) {} + bool checkAligned() const + { + return (quintptr(this) & 127) == 0; + } + + inline bool operator==(const Aligned128 &other) const { return i == other.i; } + inline bool operator<(const Aligned128 &other) const { return i < other.i; } + friend inline int qHash(const Aligned128 &a) { return qHash(a.i); } +}; + +template +void testVectorAlignment() +{ + typedef typename C::value_type Aligned; + C container; + container.append(Aligned()); + QVERIFY(container[0].checkAligned()); + + for (int i = 0; i < 200; ++i) + container.append(Aligned()); + + for (int i = 0; i < container.size(); ++i) + QVERIFY(container.at(i).checkAligned()); +} + +template +void testContiguousCacheAlignment() +{ + typedef typename C::value_type Aligned; + C container(150); + container.append(Aligned()); + QVERIFY(container[container.firstIndex()].checkAligned()); + + for (int i = 0; i < 200; ++i) + container.append(Aligned()); + + for (int i = container.firstIndex(); i < container.lastIndex(); ++i) + QVERIFY(container.at(i).checkAligned()); +} + +template +void testAssociativeContainerAlignment() +{ + typedef typename C::key_type Key; + typedef typename C::mapped_type Value; + C container; + container.insert(Key(), Value()); + + typename C::const_iterator it = container.constBegin(); + QVERIFY(it.key().checkAligned()); + QVERIFY(it.value().checkAligned()); + + // add some more elements + for (int i = 0; i < 200; ++i) + container.insert(Key(i), Value(i)); + + it = container.constBegin(); + for ( ; it != container.constEnd(); ++it) { + QVERIFY(it.key().checkAligned()); + QVERIFY(it.value().checkAligned()); + } +} + +void tst_Collections::alignment() +{ + testVectorAlignment >(); + testVectorAlignment >(); + testContiguousCacheAlignment >(); + testContiguousCacheAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); +} + +#else +void tst_Collections::alignment() +{ + QSKIP("Compiler doesn't support necessary extension keywords", SkipAll) +} +#endif + QTEST_APPLESS_MAIN(tst_Collections) #include "tst_collections.moc" -- cgit v0.12