From 1f2d0cd983d08f1b8d791cb3674b0965d5e89f1a Mon Sep 17 00:00:00 2001 From: Andrei Golubev Date: Wed, 24 Mar 2021 16:47:33 +0100 Subject: Resurrect data moves in QList Use the data moves to readjust the free space in the QList, which ultimately fixes the out-of-memory issues caused by cases like: forever { list.prepend(list.back()); list.removeLast(); } Task-number: QTBUG-91801 Task-number: QTBUG-91360 Task-number: QTBUG-93019 Change-Id: Iacff69cbf36b8b5b176bb2663df635ec972c875c Reviewed-by: Lars Knoll (cherry picked from commit a0253f5f0249024580050e4ec22d50cb139ef8d9) --- src/corelib/tools/qarraydataops.h | 56 ++++++++----- src/corelib/tools/qarraydatapointer.h | 134 ++++++++++++++++++++++++++++--- src/corelib/tools/qcontainertools_impl.h | 111 +++++++++++++++++++++++++ src/corelib/tools/qlist.h | 21 +++-- 4 files changed, 280 insertions(+), 42 deletions(-) (limited to 'src/corelib/tools') diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index 4ee09a4dfb..b70e8e4d9a 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -164,8 +164,9 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; + DataPointer oldData; - this->detachAndGrow(pos, n, &oldData); + this->detachAndGrow(pos, n, &data, &oldData); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -180,7 +181,8 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; - this->detachAndGrow(pos, n); + + this->detachAndGrow(pos, n, nullptr, nullptr); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -210,10 +212,8 @@ public: typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = QArrayData::GrowsAtBeginning; - if (detach || - (pos == QArrayData::GrowsAtBeginning && !this->freeSpaceAtBegin()) || - (pos == QArrayData::GrowsAtEnd && !this->freeSpaceAtEnd())) - this->reallocateAndGrow(pos, 1); + + this->detachAndGrow(pos, 1, nullptr, nullptr); T *where = createHole(pos, i, 1); new (where) T(std::move(tmp)); @@ -547,8 +547,9 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; + DataPointer oldData; - this->detachAndGrow(pos, n, &oldData); + this->detachAndGrow(pos, n, &data, &oldData); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -562,7 +563,8 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; - this->detachAndGrow(pos, n); + + this->detachAndGrow(pos, n, nullptr, nullptr); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -590,10 +592,8 @@ public: typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = QArrayData::GrowsAtBeginning; - if (detach || - (pos == QArrayData::GrowsAtBeginning && !this->freeSpaceAtBegin()) || - (pos == QArrayData::GrowsAtEnd && !this->freeSpaceAtEnd())) - this->reallocateAndGrow(pos, 1); + + this->detachAndGrow(pos, 1, nullptr, nullptr); Inserter(this, pos).insertOne(i, std::move(tmp)); } @@ -774,8 +774,9 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; + DataPointer oldData; - this->detachAndGrow(pos, n, &oldData); + this->detachAndGrow(pos, n, &data, &oldData); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -789,7 +790,8 @@ public: typename Data::GrowthPosition pos = Data::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = Data::GrowsAtBeginning; - this->detachAndGrow(pos, n); + + this->detachAndGrow(pos, n, nullptr, nullptr); Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); @@ -817,10 +819,8 @@ public: typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd; if (this->size != 0 && i <= (this->size >> 1)) pos = QArrayData::GrowsAtBeginning; - if (detach || - (pos == QArrayData::GrowsAtBeginning && !this->freeSpaceAtBegin()) || - (pos == QArrayData::GrowsAtEnd && !this->freeSpaceAtEnd())) - this->reallocateAndGrow(pos, 1); + + this->detachAndGrow(pos, 1, nullptr, nullptr); Inserter(this, pos).insertOne(i, std::move(tmp)); } @@ -914,6 +914,26 @@ public: ++this->size; } } + + // slightly higher level API than copyAppend() that also preallocates space + void growAppend(const T *b, const T *e) + { + if (b == e) + return; + Q_ASSERT(b < e); + const qsizetype n = e - b; + DataPointer old; + + // points into range: + if (QtPrivate::q_points_into_range(b, this->begin(), this->end())) { + this->detachAndGrow(QArrayData::GrowsAtEnd, n, &b, &old); + } else { + this->detachAndGrow(QArrayData::GrowsAtEnd, n, nullptr, nullptr); + } + Q_ASSERT(this->freeSpaceAtEnd() >= n); + // b might be updated so use [b, n) + this->copyAppend(b, b + n); + } }; } // namespace QtPrivate diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h index f6aabeee65..af60a105fe 100644 --- a/src/corelib/tools/qarraydatapointer.h +++ b/src/corelib/tools/qarraydatapointer.h @@ -166,19 +166,56 @@ public: reallocateAndGrow(QArrayData::GrowsAtEnd, 0, old); } - // pass in a pointer to a default constructed QADP, to keep it alive beyond the detach() call - void detachAndGrow(QArrayData::GrowthPosition where, qsizetype n, QArrayDataPointer *old = nullptr) + /*! \internal + + Detaches this (optionally) and grows to accommodate the free space for + \a n elements at the required side. The side is determined from \a pos. + + \a data pointer can be provided when the caller knows that \a data + points into range [this->begin(), this->end()). In case it is, *data + would be updated so that it continues to point to the element it was + pointing to before the data move. if \a data does not point into range, + one can/should pass \c nullptr. + + Similarly to \a data, \a old, pointer to a default-constructed QADP, can + be provided when the caller expects to e.g. copy the data from this to + itself: + \code + QList list(5); + qsizetype pos = getArbitraryPos(); + list.insert(pos, list.begin(), list.end()); + \endcode + + The default rule would be: \a data and \a old must either both be valid + pointers, or both equal to \c nullptr. + */ + void detachAndGrow(QArrayData::GrowthPosition where, qsizetype n, const T **data, + QArrayDataPointer *old) { - if (!needsDetach()) { - if (!n || - (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) || - (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n)) + const bool detach = needsDetach(); + bool readjusted = false; + if (!detach) { + if (!n || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) + || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n)) return; + readjusted = tryReadjustFreeSpace(where, n, data); + Q_ASSERT(!readjusted + || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) + || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n)); } - reallocateAndGrow(where, n, old); + + if (!readjusted) + reallocateAndGrow(where, n, old); } - Q_NEVER_INLINE void reallocateAndGrow(QArrayData::GrowthPosition where, qsizetype n, QArrayDataPointer *old = nullptr) + /*! \internal + + Reallocates to accommodate the free space for \a n elements at the + required side. The side is determined from \a pos. Might also shrink + when n < 0. + */ + Q_NEVER_INLINE void reallocateAndGrow(QArrayData::GrowthPosition where, qsizetype n, + QArrayDataPointer *old = nullptr) { if constexpr (QTypeInfo::isRelocatable && alignof(T) <= alignof(std::max_align_t)) { if (where == QArrayData::GrowsAtEnd && !old && !needsDetach() && n > 0) { @@ -188,9 +225,10 @@ public: } QArrayDataPointer dp(allocateGrow(*this, n, where)); + if (n > 0) + Q_CHECK_PTR(dp.data()); if (where == QArrayData::GrowsAtBeginning) { Q_ASSERT(dp.ptr); - dp.ptr += n; Q_ASSERT(dp.freeSpaceAtBegin() >= n); } else { Q_ASSERT(dp.freeSpaceAtEnd() >= n); @@ -211,6 +249,77 @@ public: old->swap(dp); } + /*! \internal + + Attempts to relocate [begin(), end()) to accommodate the free space for + \a n elements at the required side. The side is determined from \a pos. + + Returns \c true if the internal data is moved. Returns \c false when + there is no point in moving the data or the move is impossible. If \c + false is returned, it is the responsibility of the caller to figure out + how to accommodate the free space for \a n elements at \a pos. + + This function expects that certain preconditions are met, e.g. the + detach is not needed, n > 0 and so on. This is intentional to reduce the + number of if-statements when the caller knows that preconditions would + be satisfied. + + \sa reallocateAndGrow + */ + bool tryReadjustFreeSpace(QArrayData::GrowthPosition pos, qsizetype n, const T **data = nullptr) + { + Q_ASSERT(!this->needsDetach()); + Q_ASSERT(n > 0); + Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() < n) + || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() < n)); + + const qsizetype capacity = this->constAllocatedCapacity(); + const qsizetype freeAtBegin = this->freeSpaceAtBegin(); + const qsizetype freeAtEnd = this->freeSpaceAtEnd(); + + qsizetype dataStartOffset = 0; + // algorithm: + // a. GrowsAtEnd: relocate if space at begin AND size < (capacity * 2) / 3 + // [all goes to free space at end]: + // new free space at begin = 0 + // + // b. GrowsAtBeginning: relocate if space at end AND size < capacity / 3 + // [balance the free space]: + // new free space at begin = n + (total free space - n) / 2 + if (pos == QArrayData::GrowsAtEnd && freeAtBegin >= n + && ((3 * this->size) < (2 * capacity))) { + // dataStartOffset = 0; - done in declaration + } else if (pos == QArrayData::GrowsAtBeginning && freeAtEnd >= n + && ((3 * this->size) < capacity)) { + // total free space == capacity - size + dataStartOffset = n + qMax(0, (capacity - this->size - n) / 2); + } else { + // nothing to do otherwise + return false; + } + + relocate(dataStartOffset - freeAtBegin, data); + + Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() >= n) + || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() >= n)); + return true; + } + + /*! \internal + + Relocates [begin(), end()) by \a offset and updates \a data if it is not + \c nullptr and points into [begin(), end()). + */ + void relocate(qsizetype offset, const T **data = nullptr) + { + T *res = this->ptr + offset; + QtPrivate::q_relocate_overlap_n(this->ptr, this->size, res); + // first update data pointer, then this->ptr + if (data && QtPrivate::q_points_into_range(*data, this->begin(), this->end())) + *data += offset; + this->ptr = res; + } + // forwards from QArrayData qsizetype allocatedCapacity() noexcept { return d ? d->allocatedCapacity() : 0; } qsizetype constAllocatedCapacity() const noexcept { return d ? d->constAllocatedCapacity() : 0; } @@ -262,10 +371,9 @@ public: // Idea: * when growing backwards, adjust pointer to prepare free space at the beginning // * when growing forward, adjust by the previous data pointer offset - - // TODO: what's with CapacityReserved? - dataPtr += (position == QArrayData::GrowsAtBeginning) ? qMax(0, (header->alloc - from.size - n) / 2) - : from.freeSpaceAtBegin(); + dataPtr += (position == QArrayData::GrowsAtBeginning) + ? n + qMax(0, (header->alloc - from.size - n) / 2) + : from.freeSpaceAtBegin(); header->flags = from.flags(); return QArrayDataPointer(header, dataPtr); } diff --git a/src/corelib/tools/qcontainertools_impl.h b/src/corelib/tools/qcontainertools_impl.h index 465ea5c544..2053de6408 100644 --- a/src/corelib/tools/qcontainertools_impl.h +++ b/src/corelib/tools/qcontainertools_impl.h @@ -53,6 +53,7 @@ #include #include #include +#include QT_BEGIN_NAMESPACE @@ -88,6 +89,116 @@ void q_uninitialized_relocate_n(T* first, N n, T* out) } } +template +void q_relocate_overlap_n_left_move(iterator first, N n, iterator d_first) +{ + // requires: [first, n) is a valid range + // requires: d_first + n is reachable from d_first + // requires: iterator is at least a random access iterator + // requires: value_type(iterator) has a non-throwing destructor + + Q_ASSERT(n); + Q_ASSERT(d_first < first); // only allow moves to the "left" + using T = typename std::iterator_traits::value_type; + + // Watches passed iterator. Unless commit() is called, all the elements that + // the watched iterator passes through are deleted at the end of object + // lifetime. freeze() could be used to stop watching the passed iterator and + // remain at current place. + // + // requires: the iterator is expected to always point to an invalid object + // (to uninitialized memory) + struct Destructor + { + iterator *iter; + iterator end; + iterator intermediate; + + Destructor(iterator &it) noexcept : iter(std::addressof(it)), end(it) { } + void commit() noexcept { iter = std::addressof(end); } + void freeze() noexcept + { + intermediate = *iter; + iter = std::addressof(intermediate); + } + ~Destructor() noexcept + { + for (const int step = *iter < end ? 1 : -1; *iter != end;) { + std::advance(*iter, step); + (*iter)->~T(); + } + } + } destroyer(d_first); + + const iterator d_last = d_first + n; + // Note: use pair and explicitly copy iterators from it to prevent + // accidental reference semantics instead of copy. equivalent to: + // + // auto [overlapBegin, overlapEnd] = std::minmax(d_last, first); + auto pair = std::minmax(d_last, first); + + // overlap area between [d_first, d_first + n) and [first, first + n) or an + // uninitialized memory area between the two ranges + iterator overlapBegin = pair.first; + iterator overlapEnd = pair.second; + + // move construct elements in uninitialized region + while (d_first != overlapBegin) { + // account for std::reverse_iterator, cannot use new(d_first) directly + new (std::addressof(*d_first)) T(std::move_if_noexcept(*first)); + ++d_first; + ++first; + } + + // cannot commit but have to stop - there might be an overlap region + // which we don't want to delete (because it's part of existing data) + destroyer.freeze(); + + // move assign elements in overlap region + while (d_first != d_last) { + *d_first = std::move_if_noexcept(*first); + ++d_first; + ++first; + } + + Q_ASSERT(d_first == destroyer.end + n); + destroyer.commit(); // can commit here as ~T() below does not throw + + while (first != overlapEnd) + (--first)->~T(); +} + +/*! + \internal + + Relocates a range [first, n) to [d_first, n) taking care of potential memory + overlaps. This is a generic equivalent of memmove. + + If an exception is thrown during the relocation, all the relocated elements + are destroyed and [first, n) may contain valid but unspecified values, + including moved-from values (basic exception safety). +*/ +template +void q_relocate_overlap_n(T *first, N n, T *d_first) +{ + static_assert(std::is_nothrow_destructible_v, + "This algorithm requires that T has a non-throwing destructor"); + + if (n == N(0) || first == d_first || first == nullptr || d_first == nullptr) + return; + + if constexpr (QTypeInfo::isRelocatable) { + std::memmove(static_cast(d_first), static_cast(first), n * sizeof(T)); + } else { // generic version has to be used + if (d_first < first) { + q_relocate_overlap_n_left_move(first, n, d_first); + } else { // first < d_first + auto rfirst = std::make_reverse_iterator(first + n); + auto rd_first = std::make_reverse_iterator(d_first + n); + q_relocate_overlap_n_left_move(rfirst, n, rd_first); + } + } +} template using IfIsInputIterator = typename std::enable_if< diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h index 6aafb86c01..ddce07bbb7 100644 --- a/src/corelib/tools/qlist.h +++ b/src/corelib/tools/qlist.h @@ -676,9 +676,10 @@ inline void QList::resize_internal(qsizetype newSize) Q_ASSERT(newSize >= 0); if (d->needsDetach() || newSize > capacity() - d.freeSpaceAtBegin()) { - d.reallocateAndGrow(QArrayData::GrowsAtEnd, newSize - d.size); - } else if (newSize < size()) + d.detachAndGrow(QArrayData::GrowsAtEnd, newSize - d.size, nullptr, nullptr); + } else if (newSize < size()) { d->truncate(newSize); + } } template @@ -761,12 +762,7 @@ inline T QList::value(qsizetype i, parameter_type defaultValue) const template inline void QList::append(const_iterator i1, const_iterator i2) { - if (i1 == i2) - return; - const auto distance = std::distance(i1, i2); - DataPointer oldData; - d.detachAndGrow(QArrayData::GrowsAtEnd, distance, &oldData); - d->copyAppend(i1, i2); + d->growAppend(i1, i2); } template @@ -778,7 +774,9 @@ inline void QList::append(QList &&other) if (other.d->needsDetach() || !std::is_nothrow_move_constructible_v) return append(other); - d.detachAndGrow(QArrayData::GrowsAtEnd, other.size()); + // due to precondition &other != this, we can unconditionally modify 'this' + d.detachAndGrow(QArrayData::GrowsAtEnd, other.size(), nullptr, nullptr); + Q_ASSERT(d.freeSpaceAtEnd() >= other.size()); d->moveAppend(other.begin(), other.end()); } @@ -796,8 +794,9 @@ inline typename QList::iterator QList::insert(qsizetype i, qsizetype n, parameter_type t) { Q_ASSERT_X(size_t(i) <= size_t(d->size), "QList::insert", "index out of range"); - - d->insert(i, n, t); + Q_ASSERT_X(n >= 0, "QList::insert", "invalid count"); + if (Q_LIKELY(n)) + d->insert(i, n, t); return d.begin() + i; } -- cgit v1.2.3