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

9 files changed, 150 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<size_t *>(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<QContiguousCacheData *>(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<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
     }
+    int alignOfTypedData() const
+    {
+#ifdef Q_ALIGNOF
+        return qMax<int>(sizeof(void*), Q_ALIGNOF(Data));
+#else
+        return 0;
+#endif
+    }
 };
 
 template <typename T>
@@ -262,7 +273,7 @@ void QContiguousCache<T>::clear()
 template <typename T>
 inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc)
 {
-    return static_cast<QContiguousCacheData *>(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T)));
+    return QContiguousCacheData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData());
 }
 
 template <typename T>
@@ -317,7 +328,7 @@ void QContiguousCache<T>::free(Data *x)
                 i = p->array;
         }
     }
-    qFree(x);
+    x->free(x);
 }
 template <typename T>
 void QContiguousCache<T>::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<Node *>(allocateNode());
+                    Node *dup = static_cast<Node *>(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 *>(node);
     }
 
+#ifdef Q_ALIGNOF
+    static inline int alignOfNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(Node)); }
+    static inline int alignOfDummyNode() { return qMax<int>(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<Key, T> &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 <class Key, class T>
 Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
 {
-    deleteNode(reinterpret_cast<QHashData::Node*>(node));
+    deleteNode2(reinterpret_cast<QHashData::Node*>(node));
+    d->freeNode(node);
 }
 
-
 template <class Key, class T>
-Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(QHashData::Node *node)
+Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node)
 {
 #ifdef Q_CC_BOR
     concrete(node)->~QHashNode<Key, T>();
@@ -506,7 +516,6 @@ Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(QHashData::Node *node)
 #else
     concrete(node)->~Node();
 #endif
-    qFree(node);
 }
 
 template <class Key, class T>
@@ -527,9 +536,9 @@ QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anex
     Node *node;
 
     if (QTypeInfo<T>::isDummy) {
-        node = reinterpret_cast<Node *>(new (d->allocateNode()) DummyNode(akey));
+        node = reinterpret_cast<Node *>(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<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other
 template <class Key, class T>
 Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
 {
-    x->free_helper(deleteNode);
+    x->free_helper(deleteNode2);
 }
 
 template <class Key, class T>
@@ -566,8 +575,9 @@ Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
 template <class Key, class T>
 Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
 {
-    QHashData *x = d->detach_helper(duplicateNode, deleteNode,
-        QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node));
+    QHashData *x = d->detach_helper2(duplicateNode, deleteNode2,
+        QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node),
+        QTypeInfo<T>::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<Node *>(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<char *>(prev) - offset);
+        if (strictAlignment)
+            qFreeAligned(reinterpret_cast<char *>(prev) - offset);
+        else
+            qFree(reinterpret_cast<char *>(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<Node *>(reinterpret_cast<char *>(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<char *>(node) - offset);
+    if (strictAlignment)
+        qFreeAligned(reinterpret_cast<char *>(node) - offset);
+    else
+        qFree(reinterpret_cast<char *>(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<Node *>(reinterpret_cast<char *>(node) - payload());
     }
@@ -414,7 +424,7 @@ template <class Key, class T>
 Q_INLINE_TEMPLATE typename QMapData::Node *
 QMap<Key, T>::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 <class Key, class T>
 Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::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<Key, T>::operator==(const QMap<Key, T> &other) co
 template <class Key, class T>
 Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
 {
-    d = QMapData::createData();
+    d = QMapData::createData(alignment());
     d->insertInOrder = true;
     typename std::map<Key,T>::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<QVectorData *>(alignment > alignmentThreshold() ? qMallocAligned(size, alignment) : qMalloc(size));
+}
+
+QVectorData *QVectorData::reallocate(QVectorData *x, int newsize, int oldsize, int alignment)
+{
+    if (alignment > alignmentThreshold())
+        return static_cast<QVectorData *>(qReallocAligned(x, newsize, oldsize, alignment));
+    return static_cast<QVectorData *>(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<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
     }
+    inline int alignOfTypedData() const
+    {
+#ifdef Q_ALIGNOF
+        return qMax<int>(sizeof(void*), Q_ALIGNOF(Data));
+#else
+        return 0;
+#endif
+    }
 };
 
 template <typename T>
@@ -373,7 +386,7 @@ QVector<T> &QVector<T>::operator=(const QVector<T> &v)
 template <typename T>
 inline QVectorData *QVector<T>::malloc(int aalloc)
 {
-    QVectorData *vectordata = static_cast<QVectorData *>(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<T>::free(Data *x)
         while (i-- != b)
              i->~T();
     }
-    qFree(x);
+    x->free(x, alignOfTypedData());
 }
 
 template <typename T>
@@ -459,7 +472,8 @@ void QVector<T>::realloc(int asize, int aalloc)
             }
         } else {
             QT_TRY {
-                QVectorData *mem = static_cast<QVectorData *>(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;