diff options
author | Shawn Rutledge <shawn.rutledge@qt.io> | 2017-01-26 11:46:56 +0100 |
---|---|---|
committer | Shawn Rutledge <shawn.rutledge@qt.io> | 2017-01-26 11:46:56 +0100 |
commit | 9225ac7348c9023093b6ef8d4519087c7dddeaa2 (patch) | |
tree | 4660e25bd5cfd4a2a40b0ad97ea689c4acb22a8c /src/qml/memory | |
parent | 9d8fe2ac121162c15be6728495be2235b728325a (diff) | |
parent | 0076c44d3993f377ad6417d3bb08109b608dfbd2 (diff) |
Merge remote-tracking branch 'origin/dev' into wip/pointerhandler
Change-Id: I7962fd2282792c43af69784c8e98fb050fd928a7
Diffstat (limited to 'src/qml/memory')
-rw-r--r-- | src/qml/memory/memory.pri | 4 | ||||
-rw-r--r-- | src/qml/memory/qv4heap_p.h | 43 | ||||
-rw-r--r-- | src/qml/memory/qv4mm.cpp | 938 | ||||
-rw-r--r-- | src/qml/memory/qv4mm_p.h | 212 | ||||
-rw-r--r-- | src/qml/memory/qv4mmdefs_p.h | 262 |
5 files changed, 1027 insertions, 432 deletions
diff --git a/src/qml/memory/memory.pri b/src/qml/memory/memory.pri index 04b7566ccc..38fadbf23f 100644 --- a/src/qml/memory/memory.pri +++ b/src/qml/memory/memory.pri @@ -6,8 +6,8 @@ SOURCES += \ $$PWD/qv4mm.cpp \ HEADERS += \ - $$PWD/qv4mm_p.h - + $$PWD/qv4mm_p.h \ + $$PWD/qv4mmdefs_p.h } HEADERS += \ diff --git a/src/qml/memory/qv4heap_p.h b/src/qml/memory/qv4heap_p.h index 5a3797f397..8285ef4de7 100644 --- a/src/qml/memory/qv4heap_p.h +++ b/src/qml/memory/qv4heap_p.h @@ -52,6 +52,7 @@ #include <QtCore/QString> #include <private/qv4global_p.h> +#include <private/qv4mmdefs_p.h> #include <QSharedPointer> // To check if Heap::Base::init is called (meaning, all subclasses did their init and called their @@ -90,43 +91,31 @@ namespace Heap { struct Q_QML_EXPORT Base { void *operator new(size_t) = delete; - quintptr mm_data; // vtable and markbit + const VTable *vt; inline ReturnedValue asReturnedValue() const; inline void mark(QV4::ExecutionEngine *engine); - enum { - MarkBit = 0x1, - NotInUse = 0x2, - PointerMask = ~0x3 - }; - - void setVtable(const VTable *v) { - Q_ASSERT(!(mm_data & MarkBit)); - mm_data = reinterpret_cast<quintptr>(v); - } - VTable *vtable() const { - return reinterpret_cast<VTable *>(mm_data & PointerMask); - } + void setVtable(const VTable *v) { vt = v; } + const VTable *vtable() const { return vt; } inline bool isMarked() const { - return mm_data & MarkBit; + const HeapItem *h = reinterpret_cast<const HeapItem *>(this); + Chunk *c = h->chunk(); + Q_ASSERT(!Chunk::testBit(c->extendsBitmap, h - c->realBase())); + return Chunk::testBit(c->blackBitmap, h - c->realBase()); } inline void setMarkBit() { - mm_data |= MarkBit; - } - inline void clearMarkBit() { - mm_data &= ~MarkBit; + const HeapItem *h = reinterpret_cast<const HeapItem *>(this); + Chunk *c = h->chunk(); + Q_ASSERT(!Chunk::testBit(c->extendsBitmap, h - c->realBase())); + return Chunk::setBit(c->blackBitmap, h - c->realBase()); } inline bool inUse() const { - return !(mm_data & NotInUse); - } - - Base *nextFree() { - return reinterpret_cast<Base *>(mm_data & PointerMask); - } - void setNextFree(Base *m) { - mm_data = (reinterpret_cast<quintptr>(m) | NotInUse); + const HeapItem *h = reinterpret_cast<const HeapItem *>(this); + Chunk *c = h->chunk(); + Q_ASSERT(!Chunk::testBit(c->extendsBitmap, h - c->realBase())); + return Chunk::testBit(c->objectBitmap, h - c->realBase()); } void *operator new(size_t, Managed *m) { return m; } diff --git a/src/qml/memory/qv4mm.cpp b/src/qml/memory/qv4mm.cpp index 606d3ec162..6330ef6038 100644 --- a/src/qml/memory/qv4mm.cpp +++ b/src/qml/memory/qv4mm.cpp @@ -42,8 +42,12 @@ #include "qv4objectproto_p.h" #include "qv4mm_p.h" #include "qv4qobjectwrapper_p.h" +#include <QtCore/qalgorithms.h> +#include <QtCore/private/qnumeric_p.h> #include <qqmlengine.h> +#include "PageReservation.h" #include "PageAllocation.h" +#include "PageAllocationAligned.h" #include "StdLibExtras.h" #include <QElapsedTimer> @@ -56,6 +60,14 @@ #include "qv4alloca_p.h" #include "qv4profiling_p.h" +#define MM_DEBUG 0 + +#if MM_DEBUG +#define DEBUG qDebug() << "MM:" +#else +#define DEBUG if (1) ; else qDebug() << "MM:" +#endif + #ifdef V4_USE_VALGRIND #include <valgrind/valgrind.h> #include <valgrind/memcheck.h> @@ -79,319 +91,616 @@ using namespace WTF; QT_BEGIN_NAMESPACE -static uint maxShiftValue() -{ - static uint result = 0; - if (!result) { - result = 6; - if (Q_UNLIKELY(qEnvironmentVariableIsSet(QV4_MM_MAXBLOCK_SHIFT))) { - bool ok; - const uint overrideValue = qgetenv(QV4_MM_MAXBLOCK_SHIFT).toUInt(&ok); - if (ok && overrideValue <= 11 && overrideValue > 0) - result = overrideValue; +namespace QV4 { + +enum { + MinSlotsGCLimit = QV4::Chunk::AvailableSlots*16, + GCOverallocation = 200 /* Max overallocation by the GC in % */ +}; + +struct MemorySegment { + enum { + NumChunks = 8*sizeof(quint64), + SegmentSize = NumChunks*Chunk::ChunkSize, + }; + + MemorySegment(size_t size) + { + size += Chunk::ChunkSize; // make sure we can get enough 64k aligment memory + if (size < SegmentSize) + size = SegmentSize; + + pageReservation = PageReservation::reserve(size, OSAllocator::JSGCHeapPages); + base = reinterpret_cast<Chunk *>((reinterpret_cast<quintptr>(pageReservation.base()) + Chunk::ChunkSize - 1) & ~(Chunk::ChunkSize - 1)); + nChunks = NumChunks; + if (base != pageReservation.base()) + --nChunks; + } + MemorySegment(MemorySegment &&other) { + qSwap(pageReservation, other.pageReservation); + qSwap(base, other.base); + qSwap(nChunks, other.nChunks); + qSwap(allocatedMap, other.allocatedMap); + } + + ~MemorySegment() { + if (base) + pageReservation.deallocate(); + } + + void setBit(size_t index) { + Q_ASSERT(index < nChunks); + quint64 bit = static_cast<quint64>(1) << index; +// qDebug() << " setBit" << hex << index << (index & (Bits - 1)) << bit; + allocatedMap |= bit; + } + void clearBit(size_t index) { + Q_ASSERT(index < nChunks); + quint64 bit = static_cast<quint64>(1) << index; +// qDebug() << " setBit" << hex << index << (index & (Bits - 1)) << bit; + allocatedMap &= ~bit; + } + bool testBit(size_t index) const { + Q_ASSERT(index < nChunks); + quint64 bit = static_cast<quint64>(1) << index; + return (allocatedMap & bit); + } + + Chunk *allocate(size_t size); + void free(Chunk *chunk, size_t size) { + DEBUG << "freeing chunk" << chunk; + size_t index = static_cast<size_t>(chunk - base); + size_t end = index + (size - 1)/Chunk::ChunkSize + 1; + while (index < end) { + Q_ASSERT(testBit(index)); + clearBit(index); + ++index; } + + size_t pageSize = WTF::pageSize(); + size = (size + pageSize - 1) & ~(pageSize - 1); + pageReservation.decommit(chunk, size); + } + + bool contains(Chunk *c) const { + return c >= base && c < base + nChunks; } - return result; -} -static std::size_t maxChunkSizeValue() + PageReservation pageReservation; + Chunk *base = 0; + quint64 allocatedMap = 0; + uint nChunks = 0; +}; + +Chunk *MemorySegment::allocate(size_t size) { - static std::size_t result = 0; - if (!result) { - result = 32 * 1024; - if (Q_UNLIKELY(qEnvironmentVariableIsSet(QV4_MM_MAX_CHUNK_SIZE))) { - bool ok; - const std::size_t overrideValue = qgetenv(QV4_MM_MAX_CHUNK_SIZE).toUInt(&ok); - if (ok) - result = overrideValue; + size_t requiredChunks = (size + sizeof(Chunk) - 1)/sizeof(Chunk); + uint sequence = 0; + Chunk *candidate = 0; + for (uint i = 0; i < nChunks; ++i) { + if (!testBit(i)) { + if (!candidate) + candidate = base + i; + ++sequence; + } else { + candidate = 0; + sequence = 0; + } + if (sequence == requiredChunks) { + pageReservation.commit(candidate, size); + for (uint i = 0; i < requiredChunks; ++i) + setBit(candidate - base + i); + DEBUG << "allocated chunk " << candidate << hex << size; + return candidate; } } - return result; + return 0; } -using namespace QV4; - -struct MemoryManager::Data -{ - const size_t pageSize; - - struct ChunkHeader { - Heap::Base freeItems; - ChunkHeader *nextNonFull; - char *itemStart; - char *itemEnd; - unsigned itemSize; - }; +struct ChunkAllocator { + ChunkAllocator() {} - ExecutionEngine *engine; + size_t requiredChunkSize(size_t size) { + size += Chunk::HeaderSize; // space required for the Chunk header + size_t pageSize = WTF::pageSize(); + size = (size + pageSize - 1) & ~(pageSize - 1); // align to page sizes + if (size < Chunk::ChunkSize) + size = Chunk::ChunkSize; + return size; + } - std::size_t maxChunkSize; - std::vector<PageAllocation> heapChunks; - std::size_t unmanagedHeapSize; // the amount of bytes of heap that is not managed by the memory manager, but which is held onto by managed items. - std::size_t unmanagedHeapSizeGCLimit; + Chunk *allocate(size_t size = 0); + void free(Chunk *chunk, size_t size = 0); - struct LargeItem { - LargeItem *next; - size_t size; - void *data; + std::vector<MemorySegment> memorySegments; +}; - Heap::Base *heapObject() { - return reinterpret_cast<Heap::Base *>(&data); +Chunk *ChunkAllocator::allocate(size_t size) +{ + size = requiredChunkSize(size); + for (auto &m : memorySegments) { + if (~m.allocatedMap) { + Chunk *c = m.allocate(size); + if (c) + return c; } - }; + } - LargeItem *largeItems; - std::size_t totalLargeItemsAllocated; + // allocate a new segment + memorySegments.push_back(MemorySegment(size)); + Chunk *c = memorySegments.back().allocate(size); + Q_ASSERT(c); + return c; +} - enum { MaxItemSize = 512 }; - ChunkHeader *nonFullChunks[MaxItemSize/16]; - uint nChunks[MaxItemSize/16]; - uint availableItems[MaxItemSize/16]; - uint allocCount[MaxItemSize/16]; - int totalItems; - int totalAlloc; - uint maxShift; +void ChunkAllocator::free(Chunk *chunk, size_t size) +{ + size = requiredChunkSize(size); + for (auto &m : memorySegments) { + if (m.contains(chunk)) { + m.free(chunk, size); + return; + } + } + Q_ASSERT(false); +} - bool gcBlocked; - bool aggressiveGC; - bool gcStats; - bool unused; // suppress padding warning - // statistics: -#ifdef DETAILED_MM_STATS - QVector<unsigned> allocSizeCounters; -#endif // DETAILED_MM_STATS +void Chunk::sweep() +{ + // DEBUG << "sweeping chunk" << this << (*freeList); + HeapItem *o = realBase(); + for (uint i = 0; i < Chunk::EntriesInBitmap; ++i) { + Q_ASSERT((grayBitmap[i] | blackBitmap[i]) == blackBitmap[i]); // check that we don't have gray only objects + quintptr toFree = objectBitmap[i] ^ blackBitmap[i]; + Q_ASSERT((toFree & objectBitmap[i]) == toFree); // check all black objects are marked as being used + quintptr e = extendsBitmap[i]; + // DEBUG << hex << " index=" << i << toFree; + while (toFree) { + uint index = qCountTrailingZeroBits(toFree); + quintptr bit = (static_cast<quintptr>(1) << index); + + toFree ^= bit; // mask out freed slot + // DEBUG << " index" << hex << index << toFree; + + // remove all extends slots that have been freed + // this is a bit of bit trickery. + quintptr mask = (bit << 1) - 1; // create a mask of 1's to the right of and up to the current bit + quintptr objmask = e | mask; // or'ing mask with e gives all ones until the end of the current object + quintptr result = objmask + 1; + Q_ASSERT(qCountTrailingZeroBits(result) - index != 0); // ensure we freed something + result |= mask; // ensure we don't clear stuff to the right of the current object + e &= result; + + HeapItem *itemToFree = o + index; + Heap::Base *b = *itemToFree; + if (b->vtable()->destroy) { + b->vtable()->destroy(b); + b->_checkIsDestroyed(); + } + } + objectBitmap[i] = blackBitmap[i]; + blackBitmap[i] = 0; + extendsBitmap[i] = e; + o += Chunk::Bits; + } + // DEBUG << "swept chunk" << this << "freed" << slotsFreed << "slots."; +} - Data() - : pageSize(WTF::pageSize()) - , engine(0) - , maxChunkSize(maxChunkSizeValue()) - , unmanagedHeapSize(0) - , unmanagedHeapSizeGCLimit(MIN_UNMANAGED_HEAPSIZE_GC_LIMIT) - , largeItems(0) - , totalLargeItemsAllocated(0) - , totalItems(0) - , totalAlloc(0) - , maxShift(maxShiftValue()) - , gcBlocked(false) - , aggressiveGC(!qEnvironmentVariableIsEmpty("QV4_MM_AGGRESSIVE_GC")) - , gcStats(!qEnvironmentVariableIsEmpty(QV4_MM_STATS)) - { - memset(nonFullChunks, 0, sizeof(nonFullChunks)); - memset(nChunks, 0, sizeof(nChunks)); - memset(availableItems, 0, sizeof(availableItems)); - memset(allocCount, 0, sizeof(allocCount)); +void Chunk::freeAll() +{ + // DEBUG << "sweeping chunk" << this << (*freeList); + HeapItem *o = realBase(); + for (uint i = 0; i < Chunk::EntriesInBitmap; ++i) { + quintptr toFree = objectBitmap[i]; + quintptr e = extendsBitmap[i]; + // DEBUG << hex << " index=" << i << toFree; + while (toFree) { + uint index = qCountTrailingZeroBits(toFree); + quintptr bit = (static_cast<quintptr>(1) << index); + + toFree ^= bit; // mask out freed slot + // DEBUG << " index" << hex << index << toFree; + + // remove all extends slots that have been freed + // this is a bit of bit trickery. + quintptr mask = (bit << 1) - 1; // create a mask of 1's to the right of and up to the current bit + quintptr objmask = e | mask; // or'ing mask with e gives all ones until the end of the current object + quintptr result = objmask + 1; + Q_ASSERT(qCountTrailingZeroBits(result) - index != 0); // ensure we freed something + result |= mask; // ensure we don't clear stuff to the right of the current object + e &= result; + + HeapItem *itemToFree = o + index; + Heap::Base *b = *itemToFree; + if (b->vtable()->destroy) { + b->vtable()->destroy(b); + b->_checkIsDestroyed(); + } + } + objectBitmap[i] = 0; + blackBitmap[i] = 0; + extendsBitmap[i] = e; + o += Chunk::Bits; } + // DEBUG << "swept chunk" << this << "freed" << slotsFreed << "slots."; +} - ~Data() - { - for (std::vector<PageAllocation>::iterator i = heapChunks.begin(), ei = heapChunks.end(); i != ei; ++i) { - Q_V4_PROFILE_DEALLOC(engine, i->size(), Profiling::HeapPage); - i->deallocate(); +void Chunk::sortIntoBins(HeapItem **bins, uint nBins) +{ + HeapItem *base = realBase(); +#if QT_POINTER_SIZE == 8 + const int start = 0; +#else + const int start = 1; +#endif + for (int i = start; i < EntriesInBitmap; ++i) { + quintptr usedSlots = (objectBitmap[i]|extendsBitmap[i]); +#if QT_POINTER_SIZE == 8 + if (!i) + usedSlots |= (static_cast<quintptr>(1) << (HeaderSize/SlotSize)) - 1; +#endif + uint index = qCountTrailingZeroBits(usedSlots + 1); + if (index == Bits) + continue; + uint freeStart = i*Bits + index; + usedSlots &= ~((static_cast<quintptr>(1) << index) - 1); + while (i < EntriesInBitmap && !usedSlots) { + ++i; + usedSlots = (objectBitmap[i]|extendsBitmap[i]); } + if (i == EntriesInBitmap) + usedSlots = 1; + HeapItem *freeItem = base + freeStart; + + uint freeEnd = i*Bits + qCountTrailingZeroBits(usedSlots); + uint nSlots = freeEnd - freeStart; + Q_ASSERT(freeEnd > freeStart && freeEnd <= NumSlots); + freeItem->freeData.availableSlots = nSlots; + uint bin = qMin(nBins - 1, nSlots); + freeItem->freeData.next = bins[bin]; + bins[bin] = freeItem; + // DEBUG << "binnig item" << freeItem << nSlots << bin << freeItem->freeData.availableSlots; } -}; +} -namespace { -bool sweepChunk(MemoryManager::Data::ChunkHeader *header, uint *itemsInUse, ExecutionEngine *engine, std::size_t *unmanagedHeapSize) +template<typename T> +StackAllocator<T>::StackAllocator(ChunkAllocator *chunkAlloc) + : chunkAllocator(chunkAlloc) { - Q_ASSERT(unmanagedHeapSize); + chunks.push_back(chunkAllocator->allocate()); + firstInChunk = chunks.back()->first(); + nextFree = firstInChunk; + lastInChunk = firstInChunk + (Chunk::AvailableSlots - 1)/requiredSlots*requiredSlots; +} - bool isEmpty = true; - Heap::Base *tail = &header->freeItems; -// qDebug("chunkStart @ %p, size=%x, pos=%x", header->itemStart, header->itemSize, header->itemSize>>4); -#ifdef V4_USE_VALGRIND - VALGRIND_DISABLE_ERROR_REPORTING; -#endif - for (char *item = header->itemStart; item <= header->itemEnd; item += header->itemSize) { - Heap::Base *m = reinterpret_cast<Heap::Base *>(item); -// qDebug("chunk @ %p, in use: %s, mark bit: %s", -// item, (m->inUse() ? "yes" : "no"), (m->isMarked() ? "true" : "false")); - - Q_ASSERT(qintptr(item) % 16 == 0); - - if (m->isMarked()) { - Q_ASSERT(m->inUse()); - m->clearMarkBit(); - isEmpty = false; - ++(*itemsInUse); - } else { - if (m->inUse()) { -// qDebug() << "-- collecting it." << m << tail << m->nextFree(); -#ifdef V4_USE_VALGRIND - VALGRIND_ENABLE_ERROR_REPORTING; -#endif - if (std::size_t(header->itemSize) == MemoryManager::align(sizeof(Heap::String)) && m->vtable()->isString) { - std::size_t heapBytes = static_cast<Heap::String *>(m)->retainedTextSize(); - Q_ASSERT(*unmanagedHeapSize >= heapBytes); -// qDebug() << "-- it's a string holding on to" << heapBytes << "bytes"; - *unmanagedHeapSize -= heapBytes; - } +template<typename T> +void StackAllocator<T>::freeAll() +{ + for (auto c : chunks) + chunkAllocator->free(c); +} - if (m->vtable()->destroy) { - m->vtable()->destroy(m); - m->_checkIsDestroyed(); - } +template<typename T> +void StackAllocator<T>::nextChunk() { + Q_ASSERT(nextFree == lastInChunk); + ++currentChunk; + if (currentChunk >= chunks.size()) { + Chunk *newChunk = chunkAllocator->allocate(); + chunks.push_back(newChunk); + } + firstInChunk = chunks.at(currentChunk)->first(); + nextFree = firstInChunk; + lastInChunk = firstInChunk + (Chunk::AvailableSlots - 1)/requiredSlots*requiredSlots; +} - memset(m, 0, sizeof(Heap::Base)); -#ifdef V4_USE_VALGRIND - VALGRIND_DISABLE_ERROR_REPORTING; - VALGRIND_MEMPOOL_FREE(engine->memoryManager, m); +template<typename T> +void QV4::StackAllocator<T>::prevChunk() { + Q_ASSERT(nextFree == firstInChunk); + Q_ASSERT(chunks.at(currentChunk) == nextFree->chunk()); + Q_ASSERT(currentChunk > 0); + --currentChunk; + firstInChunk = chunks.at(currentChunk)->first(); + lastInChunk = firstInChunk + (Chunk::AvailableSlots - 1)/requiredSlots*requiredSlots; + nextFree = lastInChunk; +} + +template struct StackAllocator<Heap::CallContext>; + + +HeapItem *BlockAllocator::allocate(size_t size, bool forceAllocation) { + Q_ASSERT((size % Chunk::SlotSize) == 0); + size_t slotsRequired = size >> Chunk::SlotSizeShift; +#if MM_DEBUG + ++allocations[bin]; #endif -#ifdef V4_USE_HEAPTRACK - heaptrack_report_free(m); + + HeapItem **last; + + HeapItem *m; + + if (slotsRequired < NumBins - 1) { + m = freeBins[slotsRequired]; + if (m) { + freeBins[slotsRequired] = m->freeData.next; + goto done; + } + } +#if 0 + for (uint b = bin + 1; b < NumBins - 1; ++b) { + if ((m = freeBins[b])) { + Q_ASSERT(binForSlots(m->freeData.availableSlots) == b); + freeBins[b] = m->freeData.next; + // DEBUG << "looking for empty bin" << bin << "size" << size << "found" << b; + uint remainingSlots = m->freeData.availableSlots - slotsRequired; + // DEBUG << "found free slots of size" << m->freeData.availableSlots << m << "remaining" << remainingSlots; + if (remainingSlots < 2) { + // avoid too much fragmentation and rather mark the memory as used + size += remainingSlots*Chunk::SlotSize; + goto done; + } + HeapItem *remainder = m + slotsRequired; + remainder->freeData.availableSlots = remainingSlots; + uint binForRemainder = binForSlots(remainingSlots); + remainder->freeData.next = freeBins[binForRemainder]; + freeBins[binForRemainder] = remainder; + goto done; + } + } #endif - Q_V4_PROFILE_DEALLOC(engine, header->itemSize, Profiling::SmallItem); - ++(*itemsInUse); + if (nFree >= slotsRequired) { + // use bump allocation + Q_ASSERT(nextFree); + m = nextFree; + nextFree += slotsRequired; + nFree -= slotsRequired; + goto done; + } + + // DEBUG << "No matching bin found for item" << size << bin; + // search last bin for a large enough item + last = &freeBins[NumBins - 1]; + while ((m = *last)) { + if (m->freeData.availableSlots >= slotsRequired) { + *last = m->freeData.next; // take it out of the list + + size_t remainingSlots = m->freeData.availableSlots - slotsRequired; + // DEBUG << "found large free slots of size" << m->freeData.availableSlots << m << "remaining" << remainingSlots; + if (remainingSlots < 2) { + // avoid too much fragmentation and rather mark the memory as used + size += remainingSlots*Chunk::SlotSize; + goto done; + } + HeapItem *remainder = m + slotsRequired; + if (remainingSlots >= 2*NumBins) { + if (nFree) { + size_t bin = binForSlots(nFree); + nextFree->freeData.next = freeBins[bin]; + nextFree->freeData.availableSlots = nFree; + freeBins[bin] = nextFree; + } + nextFree = remainder; + nFree = remainingSlots; + } else { + remainder->freeData.availableSlots = remainingSlots; + size_t binForRemainder = binForSlots(remainingSlots); + remainder->freeData.next = freeBins[binForRemainder]; + freeBins[binForRemainder] = remainder; } - // Relink all free blocks to rewrite references to any released chunk. - tail->setNextFree(m); - tail = m; + goto done; } + last = &m->freeData.next; } - tail->setNextFree(0); -#ifdef V4_USE_VALGRIND - VALGRIND_ENABLE_ERROR_REPORTING; + + if (!m) { + if (!forceAllocation) + return 0; + Chunk *newChunk = chunkAllocator->allocate(); + chunks.push_back(newChunk); + nextFree = newChunk->first(); + nFree = Chunk::AvailableSlots; + m = nextFree; + nextFree += slotsRequired; + nFree -= slotsRequired; + } + +done: + m->setAllocatedSlots(slotsRequired); + // DEBUG << " " << hex << m->chunk() << m->chunk()->objectBitmap[0] << m->chunk()->extendsBitmap[0] << (m - m->chunk()->realBase()); + return m; +} + +void BlockAllocator::sweep() +{ + nextFree = 0; + nFree = 0; + memset(freeBins, 0, sizeof(freeBins)); + +// qDebug() << "BlockAlloc: sweep"; + usedSlotsAfterLastSweep = 0; + for (auto c : chunks) { + c->sweep(); + c->sortIntoBins(freeBins, NumBins); +// qDebug() << "used slots in chunk" << c << ":" << c->nUsedSlots(); + usedSlotsAfterLastSweep += c->nUsedSlots(); + } +} + +void BlockAllocator::freeAll() +{ + for (auto c : chunks) { + c->freeAll(); + chunkAllocator->free(c); + } +} + +#if MM_DEBUG +void BlockAllocator::stats() { + DEBUG << "MM stats:"; + QString s; + for (int i = 0; i < 10; ++i) { + uint c = 0; + HeapItem *item = freeBins[i]; + while (item) { + ++c; + item = item->freeData.next; + } + s += QString::number(c) + QLatin1String(", "); + } + HeapItem *item = freeBins[NumBins - 1]; + uint c = 0; + while (item) { + ++c; + item = item->freeData.next; + } + s += QLatin1String("..., ") + QString::number(c); + DEBUG << "bins:" << s; + QString a; + for (int i = 0; i < 10; ++i) + a += QString::number(allocations[i]) + QLatin1String(", "); + a += QLatin1String("..., ") + QString::number(allocations[NumBins - 1]); + DEBUG << "allocs:" << a; + memset(allocations, 0, sizeof(allocations)); +} #endif - return isEmpty; + + +HeapItem *HugeItemAllocator::allocate(size_t size) { + Chunk *c = chunkAllocator->allocate(size); + chunks.push_back(HugeChunk{c, size}); + Chunk::setBit(c->objectBitmap, c->first() - c->realBase()); + return c->first(); +} + +static void freeHugeChunk(ChunkAllocator *chunkAllocator, const HugeItemAllocator::HugeChunk &c) +{ + HeapItem *itemToFree = c.chunk->first(); + Heap::Base *b = *itemToFree; + if (b->vtable()->destroy) { + b->vtable()->destroy(b); + b->_checkIsDestroyed(); + } + chunkAllocator->free(c.chunk, c.size); +} + +void HugeItemAllocator::sweep() { + auto isBlack = [this] (const HugeChunk &c) { + bool b = c.chunk->first()->isBlack(); + Chunk::clearBit(c.chunk->blackBitmap, c.chunk->first() - c.chunk->realBase()); + if (!b) + freeHugeChunk(chunkAllocator, c); + return !b; + }; + + auto newEnd = std::remove_if(chunks.begin(), chunks.end(), isBlack); + chunks.erase(newEnd, chunks.end()); +} + +void HugeItemAllocator::freeAll() +{ + for (auto &c : chunks) { + freeHugeChunk(chunkAllocator, c); + } } -} // namespace MemoryManager::MemoryManager(ExecutionEngine *engine) : engine(engine) - , m_d(new Data) + , chunkAllocator(new ChunkAllocator) + , stackAllocator(chunkAllocator) + , blockAllocator(chunkAllocator) + , hugeItemAllocator(chunkAllocator) , m_persistentValues(new PersistentValueStorage(engine)) , m_weakValues(new PersistentValueStorage(engine)) + , unmanagedHeapSizeGCLimit(MIN_UNMANAGED_HEAPSIZE_GC_LIMIT) + , aggressiveGC(!qEnvironmentVariableIsEmpty("QV4_MM_AGGRESSIVE_GC")) + , gcStats(!qEnvironmentVariableIsEmpty(QV4_MM_STATS)) { #ifdef V4_USE_VALGRIND VALGRIND_CREATE_MEMPOOL(this, 0, true); #endif - m_d->engine = engine; } -Heap::Base *MemoryManager::allocData(std::size_t size, std::size_t unmanagedSize) +Heap::Base *MemoryManager::allocString(std::size_t unmanagedSize) { - if (m_d->aggressiveGC) + if (aggressiveGC) runGC(); -#ifdef DETAILED_MM_STATS - willAllocate(size); -#endif // DETAILED_MM_STATS - Q_ASSERT(size >= 16); - Q_ASSERT(size % 16 == 0); - -// qDebug() << "unmanagedHeapSize:" << m_d->unmanagedHeapSize << "limit:" << m_d->unmanagedHeapSizeGCLimit << "unmanagedSize:" << unmanagedSize; - m_d->unmanagedHeapSize += unmanagedSize; + const size_t stringSize = align(sizeof(Heap::String)); + unmanagedHeapSize += unmanagedSize; bool didGCRun = false; - if (m_d->unmanagedHeapSize > m_d->unmanagedHeapSizeGCLimit) { + if (unmanagedHeapSize > unmanagedHeapSizeGCLimit) { runGC(); - if (3*m_d->unmanagedHeapSizeGCLimit <= 4*m_d->unmanagedHeapSize) + if (3*unmanagedHeapSizeGCLimit <= 4*unmanagedHeapSize) // more than 75% full, raise limit - m_d->unmanagedHeapSizeGCLimit = std::max(m_d->unmanagedHeapSizeGCLimit, m_d->unmanagedHeapSize) * 2; - else if (m_d->unmanagedHeapSize * 4 <= m_d->unmanagedHeapSizeGCLimit) + unmanagedHeapSizeGCLimit = std::max(unmanagedHeapSizeGCLimit, unmanagedHeapSize) * 2; + else if (unmanagedHeapSize * 4 <= unmanagedHeapSizeGCLimit) // less than 25% full, lower limit - m_d->unmanagedHeapSizeGCLimit = qMax(MIN_UNMANAGED_HEAPSIZE_GC_LIMIT, m_d->unmanagedHeapSizeGCLimit/2); + unmanagedHeapSizeGCLimit = qMax(MIN_UNMANAGED_HEAPSIZE_GC_LIMIT, unmanagedHeapSizeGCLimit/2); didGCRun = true; } - size_t pos = size >> 4; - - // doesn't fit into a small bucket - if (size >= MemoryManager::Data::MaxItemSize) { - if (!didGCRun && m_d->totalLargeItemsAllocated > 8 * 1024 * 1024) + HeapItem *m = blockAllocator.allocate(stringSize); + if (!m) { + if (!didGCRun && shouldRunGC()) runGC(); - - // we use malloc for this - const size_t totalSize = size + sizeof(MemoryManager::Data::LargeItem); - Q_V4_PROFILE_ALLOC(engine, totalSize, Profiling::LargeItem); - MemoryManager::Data::LargeItem *item = - static_cast<MemoryManager::Data::LargeItem *>(malloc(totalSize)); - memset(item, 0, totalSize); - item->next = m_d->largeItems; - item->size = size; - m_d->largeItems = item; - m_d->totalLargeItemsAllocated += size; - return item->heapObject(); + m = blockAllocator.allocate(stringSize, true); } - Heap::Base *m = 0; - Data::ChunkHeader *header = m_d->nonFullChunks[pos]; - if (header) { - m = header->freeItems.nextFree(); - goto found; - } + memset(m, 0, stringSize); + return *m; +} - // try to free up space, otherwise allocate - if (!didGCRun && m_d->allocCount[pos] > (m_d->availableItems[pos] >> 1) && m_d->totalAlloc > (m_d->totalItems >> 1) && !m_d->aggressiveGC) { +Heap::Base *MemoryManager::allocData(std::size_t size) +{ + if (aggressiveGC) runGC(); - header = m_d->nonFullChunks[pos]; - if (header) { - m = header->freeItems.nextFree(); - goto found; - } - } +#ifdef DETAILED_MM_STATS + willAllocate(size); +#endif // DETAILED_MM_STATS - // no free item available, allocate a new chunk - { - // allocate larger chunks at a time to avoid excessive GC, but cap at maximum chunk size (2MB by default) - uint shift = ++m_d->nChunks[pos]; - if (shift > m_d->maxShift) - shift = m_d->maxShift; - std::size_t allocSize = m_d->maxChunkSize*(size_t(1) << shift); - allocSize = roundUpToMultipleOf(m_d->pageSize, allocSize); - Q_V4_PROFILE_ALLOC(engine, allocSize, Profiling::HeapPage); - PageAllocation allocation = PageAllocation::allocate(allocSize, OSAllocator::JSGCHeapPages); - m_d->heapChunks.push_back(allocation); - - header = reinterpret_cast<Data::ChunkHeader *>(allocation.base()); - Q_ASSERT(size <= UINT_MAX); - header->itemSize = unsigned(size); - header->itemStart = reinterpret_cast<char *>(allocation.base()) + roundUpToMultipleOf(16, sizeof(Data::ChunkHeader)); - header->itemEnd = reinterpret_cast<char *>(allocation.base()) + allocation.size() - header->itemSize; - - header->nextNonFull = m_d->nonFullChunks[pos]; - m_d->nonFullChunks[pos] = header; - - Heap::Base *last = &header->freeItems; - for (char *item = header->itemStart; item <= header->itemEnd; item += header->itemSize) { - Heap::Base *o = reinterpret_cast<Heap::Base *>(item); - last->setNextFree(o); - last = o; + Q_ASSERT(size >= Chunk::SlotSize); + Q_ASSERT(size % Chunk::SlotSize == 0); - } - last->setNextFree(0); - m = header->freeItems.nextFree(); - Q_ASSERT(header->itemEnd >= header->itemStart); - const size_t increase = quintptr(header->itemEnd - header->itemStart) / header->itemSize; - m_d->availableItems[pos] += uint(increase); - m_d->totalItems += int(increase); -#ifdef V4_USE_VALGRIND - VALGRIND_MAKE_MEM_NOACCESS(allocation.base(), allocSize); - VALGRIND_MEMPOOL_ALLOC(this, header, sizeof(Data::ChunkHeader)); -#endif -#ifdef V4_USE_HEAPTRACK - heaptrack_report_alloc(header, sizeof(Data::ChunkHeader)); -#endif +// qDebug() << "unmanagedHeapSize:" << unmanagedHeapSize << "limit:" << unmanagedHeapSizeGCLimit << "unmanagedSize:" << unmanagedSize; + + if (size > Chunk::DataSize) + return *hugeItemAllocator.allocate(size); + + HeapItem *m = blockAllocator.allocate(size); + if (!m) { + if (shouldRunGC()) + runGC(); + m = blockAllocator.allocate(size, true); } - found: -#ifdef V4_USE_VALGRIND - VALGRIND_MEMPOOL_ALLOC(this, m, size); -#endif -#ifdef V4_USE_HEAPTRACK - heaptrack_report_alloc(m, size); -#endif - Q_V4_PROFILE_ALLOC(engine, size, Profiling::SmallItem); + memset(m, 0, size); + return *m; +} - ++m_d->allocCount[pos]; - ++m_d->totalAlloc; - header->freeItems.setNextFree(m->nextFree()); - if (!header->freeItems.nextFree()) - m_d->nonFullChunks[pos] = header->nextNonFull; - return m; +Heap::Object *MemoryManager::allocObjectWithMemberData(std::size_t size, uint nMembers) +{ + Heap::Object *o = static_cast<Heap::Object *>(allocData(size)); + + // ### Could optimize this and allocate both in one go through the block allocator + if (nMembers) { + std::size_t memberSize = align(sizeof(Heap::MemberData) + (nMembers - 1)*sizeof(Value)); +// qDebug() << "allocating member data for" << o << nMembers << memberSize; + Heap::Base *m; + if (memberSize > Chunk::DataSize) + m = *hugeItemAllocator.allocate(memberSize); + else + m = *blockAllocator.allocate(memberSize, true); + memset(m, 0, memberSize); + o->memberData = static_cast<Heap::MemberData *>(m); + o->memberData->setVtable(MemberData::staticVTable()); + o->memberData->size = static_cast<uint>((memberSize - sizeof(Heap::MemberData) + sizeof(Value))/sizeof(Value)); + o->memberData->init(); +// qDebug() << " got" << o->memberData << o->memberData->size; + } + return o; } static void drainMarkStack(QV4::ExecutionEngine *engine, Value *markBase) @@ -495,98 +804,34 @@ void MemoryManager::sweep(bool lastSweep) } } - bool *chunkIsEmpty = static_cast<bool *>(alloca(m_d->heapChunks.size() * sizeof(bool))); - uint itemsInUse[MemoryManager::Data::MaxItemSize/16]; - memset(itemsInUse, 0, sizeof(itemsInUse)); - memset(m_d->nonFullChunks, 0, sizeof(m_d->nonFullChunks)); - - for (size_t i = 0; i < m_d->heapChunks.size(); ++i) { - Data::ChunkHeader *header = reinterpret_cast<Data::ChunkHeader *>(m_d->heapChunks[i].base()); - chunkIsEmpty[i] = sweepChunk(header, &itemsInUse[header->itemSize >> 4], engine, &m_d->unmanagedHeapSize); - } - - std::vector<PageAllocation>::iterator chunkIter = m_d->heapChunks.begin(); - for (size_t i = 0; i < m_d->heapChunks.size(); ++i) { - Q_ASSERT(chunkIter != m_d->heapChunks.end()); - Data::ChunkHeader *header = reinterpret_cast<Data::ChunkHeader *>(chunkIter->base()); - const size_t pos = header->itemSize >> 4; - Q_ASSERT(header->itemEnd >= header->itemStart); - const size_t decrease = quintptr(header->itemEnd - header->itemStart) / header->itemSize; - - // Release that chunk if it could have been spared since the last GC run without any difference. - if (chunkIsEmpty[i] && m_d->availableItems[pos] - decrease >= itemsInUse[pos]) { - Q_V4_PROFILE_DEALLOC(engine, chunkIter->size(), Profiling::HeapPage); -#ifdef V4_USE_VALGRIND - VALGRIND_MEMPOOL_FREE(this, header); -#endif -#ifdef V4_USE_HEAPTRACK - heaptrack_report_free(header); -#endif - --m_d->nChunks[pos]; - m_d->availableItems[pos] -= uint(decrease); - m_d->totalItems -= int(decrease); - chunkIter->deallocate(); - chunkIter = m_d->heapChunks.erase(chunkIter); - continue; - } else if (header->freeItems.nextFree()) { - header->nextNonFull = m_d->nonFullChunks[pos]; - m_d->nonFullChunks[pos] = header; - } - ++chunkIter; - } - - Data::LargeItem *i = m_d->largeItems; - Data::LargeItem **last = &m_d->largeItems; - while (i) { - Heap::Base *m = i->heapObject(); - Q_ASSERT(m->inUse()); - if (m->isMarked()) { - m->clearMarkBit(); - last = &i->next; - i = i->next; - continue; - } - if (m->vtable()->destroy) - m->vtable()->destroy(m); - - *last = i->next; - Q_V4_PROFILE_DEALLOC(engine, i->size + sizeof(Data::LargeItem), Profiling::LargeItem); - free(i); - i = *last; - } - - // some execution contexts are allocated on the stack, make sure we clear their markBit as well - if (!lastSweep) { - QV4::ExecutionContext *ctx = engine->currentContext; - while (ctx) { - ctx->d()->clearMarkBit(); - ctx = engine->parentContext(ctx); - } - } + blockAllocator.sweep(); + hugeItemAllocator.sweep(); } -bool MemoryManager::isGCBlocked() const +bool MemoryManager::shouldRunGC() const { - return m_d->gcBlocked; + size_t total = blockAllocator.totalSlots(); + size_t usedSlots = blockAllocator.usedSlotsAfterLastSweep; + if (total > MinSlotsGCLimit && usedSlots * GCOverallocation < total * 100) + return true; + return false; } -void MemoryManager::setGCBlocked(bool blockGC) -{ - m_d->gcBlocked = blockGC; -} void MemoryManager::runGC() { - if (m_d->gcBlocked) { + if (gcBlocked) { // qDebug() << "Not running GC."; return; } - QScopedValueRollback<bool> gcBlocker(m_d->gcBlocked, true); + QScopedValueRollback<bool> gcBlocker(gcBlocked, true); - if (!m_d->gcStats) { + if (!gcStats) { +// uint oldUsed = allocator.usedMem(); mark(); sweep(); +// DEBUG << "RUN GC: allocated:" << allocator.allocatedMem() << "used before" << oldUsed << "used now" << allocator.usedMem(); } else { const size_t totalMem = getAllocatedMem(); @@ -596,7 +841,6 @@ void MemoryManager::runGC() qint64 markTime = t.restart(); const size_t usedBefore = getUsedMem(); const size_t largeItemsBefore = getLargeItemsMem(); - size_t chunksBefore = m_d->heapChunks.size(); sweep(); const size_t usedAfter = getUsedMem(); const size_t largeItemsAfter = getLargeItemsMem(); @@ -605,56 +849,30 @@ void MemoryManager::runGC() qDebug() << "========== GC =========="; qDebug() << "Marked object in" << markTime << "ms."; qDebug() << "Sweeped object in" << sweepTime << "ms."; - qDebug() << "Allocated" << totalMem << "bytes in" << m_d->heapChunks.size() << "chunks."; + qDebug() << "Allocated" << totalMem << "bytes"; qDebug() << "Used memory before GC:" << usedBefore; qDebug() << "Used memory after GC:" << usedAfter; qDebug() << "Freed up bytes:" << (usedBefore - usedAfter); - qDebug() << "Released chunks:" << (chunksBefore - m_d->heapChunks.size()); qDebug() << "Large item memory before GC:" << largeItemsBefore; qDebug() << "Large item memory after GC:" << largeItemsAfter; qDebug() << "Large item memory freed up:" << (largeItemsBefore - largeItemsAfter); qDebug() << "======== End GC ========"; } - - memset(m_d->allocCount, 0, sizeof(m_d->allocCount)); - m_d->totalAlloc = 0; - m_d->totalLargeItemsAllocated = 0; } size_t MemoryManager::getUsedMem() const { - size_t usedMem = 0; - for (std::vector<PageAllocation>::const_iterator i = m_d->heapChunks.cbegin(), ei = m_d->heapChunks.cend(); i != ei; ++i) { - Data::ChunkHeader *header = reinterpret_cast<Data::ChunkHeader *>(i->base()); - for (char *item = header->itemStart; item <= header->itemEnd; item += header->itemSize) { - Heap::Base *m = reinterpret_cast<Heap::Base *>(item); - Q_ASSERT(qintptr(item) % 16 == 0); - if (m->inUse()) - usedMem += header->itemSize; - } - } - return usedMem; + return blockAllocator.usedMem(); } size_t MemoryManager::getAllocatedMem() const { - size_t total = 0; - for (size_t i = 0; i < m_d->heapChunks.size(); ++i) - total += m_d->heapChunks.at(i).size(); - return total; + return blockAllocator.allocatedMem() + hugeItemAllocator.usedMem(); } size_t MemoryManager::getLargeItemsMem() const { - size_t total = 0; - for (const Data::LargeItem *i = m_d->largeItems; i != 0; i = i->next) - total += i->size; - return total; -} - -void MemoryManager::growUnmanagedHeapSizeUsage(size_t delta) -{ - m_d->unmanagedHeapSize += delta; + return hugeItemAllocator.usedMem(); } MemoryManager::~MemoryManager() @@ -662,23 +880,26 @@ MemoryManager::~MemoryManager() delete m_persistentValues; sweep(/*lastSweep*/true); + blockAllocator.freeAll(); + hugeItemAllocator.freeAll(); + stackAllocator.freeAll(); delete m_weakValues; #ifdef V4_USE_VALGRIND VALGRIND_DESTROY_MEMPOOL(this); #endif + delete chunkAllocator; } - void MemoryManager::dumpStats() const { #ifdef DETAILED_MM_STATS std::cerr << "=================" << std::endl; std::cerr << "Allocation stats:" << std::endl; std::cerr << "Requests for each chunk size:" << std::endl; - for (int i = 0; i < m_d->allocSizeCounters.size(); ++i) { - if (unsigned count = m_d->allocSizeCounters[i]) { + for (int i = 0; i < allocSizeCounters.size(); ++i) { + if (unsigned count = allocSizeCounters[i]) { std::cerr << "\t" << (i << 4) << " bytes chunks: " << count << std::endl; } } @@ -689,7 +910,7 @@ void MemoryManager::dumpStats() const void MemoryManager::willAllocate(std::size_t size) { unsigned alignedSize = (size + 15) >> 4; - QVector<unsigned> &counters = m_d->allocSizeCounters; + QVector<unsigned> &counters = allocSizeCounters; if ((unsigned) counters.size() < alignedSize + 1) counters.resize(alignedSize + 1); counters[alignedSize]++; @@ -709,4 +930,7 @@ void MemoryManager::collectFromJSStack() const ++v; } } + +} // namespace QV4 + QT_END_NAMESPACE diff --git a/src/qml/memory/qv4mm_p.h b/src/qml/memory/qv4mm_p.h index dfa0d85dff..00daf8a622 100644 --- a/src/qml/memory/qv4mm_p.h +++ b/src/qml/memory/qv4mm_p.h @@ -55,6 +55,7 @@ #include <private/qv4value_p.h> #include <private/qv4scopedvalue_p.h> #include <private/qv4object_p.h> +#include <private/qv4mmdefs_p.h> #include <QVector> //#define DETAILED_MM_STATS @@ -63,55 +64,166 @@ #define QV4_MM_MAX_CHUNK_SIZE "QV4_MM_MAX_CHUNK_SIZE" #define QV4_MM_STATS "QV4_MM_STATS" +#define MM_DEBUG 0 + QT_BEGIN_NAMESPACE namespace QV4 { -struct GCDeletable; +struct ChunkAllocator; -class Q_QML_EXPORT MemoryManager -{ - Q_DISABLE_COPY(MemoryManager); +template<typename T> +struct StackAllocator { + Q_STATIC_ASSERT(sizeof(T) < Chunk::DataSize); + static const uint requiredSlots = (sizeof(T) + sizeof(HeapItem) - 1)/sizeof(HeapItem); -public: - struct Data; + StackAllocator(ChunkAllocator *chunkAlloc); - class GCBlocker - { - public: - GCBlocker(MemoryManager *mm) - : mm(mm) - , wasBlocked(mm->isGCBlocked()) - { - mm->setGCBlocked(true); + T *allocate() { + T *m = nextFree->as<T>(); + if (Q_UNLIKELY(nextFree == lastInChunk)) { + nextChunk(); + } else { + nextFree += requiredSlots; } - - ~GCBlocker() - { - mm->setGCBlocked(wasBlocked); +#if MM_DEBUG + Chunk *c = m->chunk(); + Chunk::setBit(c->objectBitmap, m - c->realBase()); +#endif + return m; + } + void free() { +#if MM_DEBUG + Chunk::clearBit(item->chunk()->objectBitmap, item - item->chunk()->realBase()); +#endif + if (Q_UNLIKELY(nextFree == firstInChunk)) { + prevChunk(); + } else { + nextFree -= requiredSlots; } + } + + void nextChunk(); + void prevChunk(); + + void freeAll(); + + ChunkAllocator *chunkAllocator; + HeapItem *nextFree = 0; + HeapItem *firstInChunk = 0; + HeapItem *lastInChunk = 0; + std::vector<Chunk *> chunks; + uint currentChunk = 0; +}; + +struct BlockAllocator { + BlockAllocator(ChunkAllocator *chunkAllocator) + : chunkAllocator(chunkAllocator) + { + memset(freeBins, 0, sizeof(freeBins)); +#if MM_DEBUG + memset(allocations, 0, sizeof(allocations)); +#endif + } + + enum { NumBins = 8 }; + + static inline size_t binForSlots(size_t nSlots) { + return nSlots >= NumBins ? NumBins - 1 : nSlots; + } + +#if MM_DEBUG + void stats(); +#endif + + HeapItem *allocate(size_t size, bool forceAllocation = false); + + size_t totalSlots() const { + return Chunk::AvailableSlots*chunks.size(); + } + + size_t allocatedMem() const { + return chunks.size()*Chunk::DataSize; + } + size_t usedMem() const { + uint used = 0; + for (auto c : chunks) + used += c->nUsedSlots()*Chunk::SlotSize; + return used; + } - private: - MemoryManager *mm; - bool wasBlocked; + void sweep(); + void freeAll(); + + // bump allocations + HeapItem *nextFree = 0; + size_t nFree = 0; + size_t usedSlotsAfterLastSweep = 0; + HeapItem *freeBins[NumBins]; + ChunkAllocator *chunkAllocator; + std::vector<Chunk *> chunks; +#if MM_DEBUG + uint allocations[NumBins]; +#endif +}; + +struct HugeItemAllocator { + HugeItemAllocator(ChunkAllocator *chunkAllocator) + : chunkAllocator(chunkAllocator) + {} + + HeapItem *allocate(size_t size); + void sweep(); + void freeAll(); + + size_t usedMem() const { + size_t used = 0; + for (const auto &c : chunks) + used += c.size; + return used; + } + + ChunkAllocator *chunkAllocator; + struct HugeChunk { + Chunk *chunk; + size_t size; }; + std::vector<HugeChunk> chunks; +}; + + +class Q_QML_EXPORT MemoryManager +{ + Q_DISABLE_COPY(MemoryManager); + public: MemoryManager(ExecutionEngine *engine); ~MemoryManager(); // TODO: this is only for 64bit (and x86 with SSE/AVX), so exend it for other architectures to be slightly more efficient (meaning, align on 8-byte boundaries). // Note: all occurrences of "16" in alloc/dealloc are also due to the alignment. - static inline std::size_t align(std::size_t size) - { return (size + 15) & ~0xf; } + Q_DECL_CONSTEXPR static inline std::size_t align(std::size_t size) + { return (size + Chunk::SlotSize - 1) & ~(Chunk::SlotSize - 1); } + + QV4::Heap::CallContext *allocSimpleCallContext(QV4::ExecutionEngine *v4) + { + Heap::CallContext *ctxt = stackAllocator.allocate(); + memset(ctxt, 0, sizeof(Heap::CallContext)); + ctxt->setVtable(QV4::CallContext::staticVTable()); + ctxt->init(v4); + return ctxt; + + } + void freeSimpleCallContext() + { stackAllocator.free(); } template<typename ManagedType> - inline typename ManagedType::Data *allocManaged(std::size_t size, std::size_t unmanagedSize = 0) + inline typename ManagedType::Data *allocManaged(std::size_t size) { V4_ASSERT_IS_TRIVIAL(typename ManagedType::Data) size = align(size); - Heap::Base *o = allocData(size, unmanagedSize); - memset(o, 0, size); + Heap::Base *o = allocData(size); o->setVtable(ManagedType::staticVTable()); return static_cast<typename ManagedType::Data *>(o); } @@ -119,35 +231,31 @@ public: template <typename ObjectType> typename ObjectType::Data *allocateObject(InternalClass *ic) { - const int size = (sizeof(typename ObjectType::Data) + (sizeof(Value) - 1)) & ~(sizeof(Value) - 1); - typename ObjectType::Data *o = allocManaged<ObjectType>(size + ic->size*sizeof(Value)); + Heap::Object *o = allocObjectWithMemberData(align(sizeof(typename ObjectType::Data)), ic->size); + o->setVtable(ObjectType::staticVTable()); o->internalClass = ic; - o->inlineMemberSize = ic->size; - o->inlineMemberOffset = size/sizeof(Value); - return o; + return static_cast<typename ObjectType::Data *>(o); } template <typename ObjectType> typename ObjectType::Data *allocateObject() { InternalClass *ic = ObjectType::defaultInternalClass(engine); - const int size = (sizeof(typename ObjectType::Data) + (sizeof(Value) - 1)) & ~(sizeof(Value) - 1); - typename ObjectType::Data *o = allocManaged<ObjectType>(size + ic->size*sizeof(Value)); + Heap::Object *o = allocObjectWithMemberData(align(sizeof(typename ObjectType::Data)), ic->size); + o->setVtable(ObjectType::staticVTable()); Object *prototype = ObjectType::defaultPrototype(engine); o->internalClass = ic; o->prototype = prototype->d(); - o->inlineMemberSize = ic->size; - o->inlineMemberOffset = size/sizeof(Value); - return o; + return static_cast<typename ObjectType::Data *>(o); } template <typename ManagedType, typename Arg1> typename ManagedType::Data *allocWithStringData(std::size_t unmanagedSize, Arg1 arg1) { - Scope scope(engine); - Scoped<ManagedType> t(scope, allocManaged<ManagedType>(sizeof(typename ManagedType::Data), unmanagedSize)); - t->d_unchecked()->init(this, arg1); - return t->d(); + typename ManagedType::Data *o = reinterpret_cast<typename ManagedType::Data *>(allocString(unmanagedSize)); + o->setVtable(ManagedType::staticVTable()); + o->init(this, arg1); + return o; } template <typename ObjectType> @@ -309,8 +417,6 @@ public: return t->d(); } - bool isGCBlocked() const; - void setGCBlocked(bool blockGC); void runGC(); void dumpStats() const; @@ -319,12 +425,15 @@ public: size_t getAllocatedMem() const; size_t getLargeItemsMem() const; - void growUnmanagedHeapSizeUsage(size_t delta); // called when a JS object grows itself. Specifically: Heap::String::append + // called when a JS object grows itself. Specifically: Heap::String::append + void changeUnmanagedHeapSizeUsage(qptrdiff delta) { unmanagedHeapSize += delta; } + protected: /// expects size to be aligned - // TODO: try to inline - Heap::Base *allocData(std::size_t size, std::size_t unmanagedSize); + Heap::Base *allocString(std::size_t unmanagedSize); + Heap::Base *allocData(std::size_t size); + Heap::Object *allocObjectWithMemberData(std::size_t size, uint nMembers); #ifdef DETAILED_MM_STATS void willAllocate(std::size_t size); @@ -334,13 +443,24 @@ private: void collectFromJSStack() const; void mark(); void sweep(bool lastSweep = false); + bool shouldRunGC() const; public: QV4::ExecutionEngine *engine; - QScopedPointer<Data> m_d; + ChunkAllocator *chunkAllocator; + StackAllocator<Heap::CallContext> stackAllocator; + BlockAllocator blockAllocator; + HugeItemAllocator hugeItemAllocator; PersistentValueStorage *m_persistentValues; PersistentValueStorage *m_weakValues; QVector<Value *> m_pendingFreedObjectWrapperValue; + + std::size_t unmanagedHeapSize = 0; // the amount of bytes of heap that is not managed by the memory manager, but which is held onto by managed items. + std::size_t unmanagedHeapSizeGCLimit; + + bool gcBlocked = false; + bool aggressiveGC = false; + bool gcStats = false; }; } diff --git a/src/qml/memory/qv4mmdefs_p.h b/src/qml/memory/qv4mmdefs_p.h new file mode 100644 index 0000000000..588ae21ee0 --- /dev/null +++ b/src/qml/memory/qv4mmdefs_p.h @@ -0,0 +1,262 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ +#ifndef QV4MMDEFS_P_H +#define QV4MMDEFS_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <private/qv4global_p.h> +#include <QtCore/qalgorithms.h> +#include <qdebug.h> + +QT_BEGIN_NAMESPACE + +namespace QV4 { + +/* + * Chunks are the basic structure containing GC managed objects. + * + * Chunks are 64k aligned in memory, so that retrieving the Chunk pointer from a Heap object + * is a simple masking operation. Each Chunk has 4 bitmaps for managing purposes, + * and 32byte wide slots for the objects following afterwards. + * + * The gray and black bitmaps are used for mark/sweep. + * The object bitmap has a bit set if this location represents the start of a Heap object. + * The extends bitmap denotes the extend of an object. It has a cleared bit at the start of the object + * and a set bit for all following slots used by the object. + * + * Free memory has both used and extends bits set to 0. + * + * This gives the following operations when allocating an object of size s: + * Find s/Alignment consecutive free slots in the chunk. Set the object bit for the first + * slot to 1. Set the extends bits for all following slots to 1. + * + * All used slots can be found by object|extents. + * + * When sweeping, simply copy the black bits over to the object bits. + * + */ +struct HeapItem; +struct Chunk { + enum { + ChunkSize = 64*1024, + ChunkShift = 16, + SlotSize = 32, + SlotSizeShift = 5, + NumSlots = ChunkSize/SlotSize, + BitmapSize = NumSlots/8, + HeaderSize = 4*BitmapSize, + DataSize = ChunkSize - HeaderSize, + AvailableSlots = DataSize/SlotSize, +#if QT_POINTER_SIZE == 8 + Bits = 64, + BitShift = 6, +#else + Bits = 32, + BitShift = 5, +#endif + EntriesInBitmap = BitmapSize/sizeof(quintptr) + }; + quintptr grayBitmap[BitmapSize/sizeof(quintptr)]; + quintptr blackBitmap[BitmapSize/sizeof(quintptr)]; + quintptr objectBitmap[BitmapSize/sizeof(quintptr)]; + quintptr extendsBitmap[BitmapSize/sizeof(quintptr)]; + char data[ChunkSize - HeaderSize]; + + HeapItem *realBase(); + HeapItem *first(); + + static void setBit(quintptr *bitmap, size_t index) { +// Q_ASSERT(index >= HeaderSize/SlotSize && index < ChunkSize/SlotSize); + bitmap += index >> BitShift; + quintptr bit = static_cast<quintptr>(1) << (index & (Bits - 1)); + *bitmap |= bit; + } + static void clearBit(quintptr *bitmap, size_t index) { +// Q_ASSERT(index >= HeaderSize/SlotSize && index < ChunkSize/SlotSize); + bitmap += index >> BitShift; + quintptr bit = static_cast<quintptr>(1) << (index & (Bits - 1)); + *bitmap &= ~bit; + } + static bool testBit(quintptr *bitmap, size_t index) { +// Q_ASSERT(index >= HeaderSize/SlotSize && index < ChunkSize/SlotSize); + bitmap += index >> BitShift; + quintptr bit = static_cast<quintptr>(1) << (index & (Bits - 1)); + return (*bitmap & bit); + } + static void setBits(quintptr *bitmap, size_t index, size_t nBits) { +// Q_ASSERT(index >= HeaderSize/SlotSize && index + nBits <= ChunkSize/SlotSize); + if (!nBits) + return; + bitmap += index >> BitShift; + index &= (Bits - 1); + while (1) { + size_t bitsToSet = qMin(nBits, Bits - index); + quintptr mask = static_cast<quintptr>(-1) >> (Bits - bitsToSet) << index; + *bitmap |= mask; + nBits -= bitsToSet; + if (!nBits) + return; + index = 0; + ++bitmap; + } + } + static bool hasNonZeroBit(quintptr *bitmap) { + for (uint i = 0; i < EntriesInBitmap; ++i) + if (bitmap[i]) + return true; + return false; + } + static uint lowestNonZeroBit(quintptr *bitmap) { + for (uint i = 0; i < EntriesInBitmap; ++i) { + if (bitmap[i]) { + quintptr b = bitmap[i]; + return i*Bits + qCountTrailingZeroBits(b); + } + } + return 0; + } + + uint nFreeSlots() const { + return AvailableSlots - nUsedSlots(); + } + uint nUsedSlots() const { + uint usedSlots = 0; + for (uint i = 0; i < EntriesInBitmap; ++i) { + quintptr used = objectBitmap[i] | extendsBitmap[i]; + usedSlots += qPopulationCount(used); + } + return usedSlots; + } + + void sweep(); + void freeAll(); + + void sortIntoBins(HeapItem **bins, uint nBins); +}; + +struct HeapItem { + union { + struct { + HeapItem *next; + size_t availableSlots; + } freeData; + quint64 payload[Chunk::SlotSize/sizeof(quint64)]; + }; + operator Heap::Base *() { return reinterpret_cast<Heap::Base *>(this); } + + template<typename T> + T *as() { return static_cast<T *>(reinterpret_cast<Heap::Base *>(this)); } + + Chunk *chunk() const { + return reinterpret_cast<Chunk *>(reinterpret_cast<quintptr>(this) >> Chunk::ChunkShift << Chunk::ChunkShift); + } + + bool isGray() const { + Chunk *c = chunk(); + uint index = this - c->realBase(); + return Chunk::testBit(c->grayBitmap, index); + } + bool isBlack() const { + Chunk *c = chunk(); + uint index = this - c->realBase(); + return Chunk::testBit(c->blackBitmap, index); + } + bool isInUse() const { + Chunk *c = chunk(); + uint index = this - c->realBase(); + return Chunk::testBit(c->objectBitmap, index); + } + + void setAllocatedSlots(size_t nSlots) { +// Q_ASSERT(size && !(size % sizeof(HeapItem))); + Chunk *c = chunk(); + size_t index = this - c->realBase(); +// Q_ASSERT(!Chunk::testBit(c->objectBitmap, index)); + Chunk::setBit(c->objectBitmap, index); + Chunk::setBits(c->extendsBitmap, index + 1, nSlots - 1); +// for (uint i = index + 1; i < nBits - 1; ++i) +// Q_ASSERT(Chunk::testBit(c->extendsBitmap, i)); +// Q_ASSERT(!Chunk::testBit(c->extendsBitmap, index)); + } + + // Doesn't report correctly for huge items + size_t size() const { + Chunk *c = chunk(); + uint index = this - c->realBase(); + Q_ASSERT(Chunk::testBit(c->objectBitmap, index)); + // ### optimize me + uint end = index + 1; + while (end < Chunk::NumSlots && Chunk::testBit(c->extendsBitmap, end)) + ++end; + return (end - index)*sizeof(HeapItem); + } +}; + +inline HeapItem *Chunk::realBase() +{ + return reinterpret_cast<HeapItem *>(this); +} + +inline HeapItem *Chunk::first() +{ + return reinterpret_cast<HeapItem *>(data); +} + +Q_STATIC_ASSERT(sizeof(Chunk) == Chunk::ChunkSize); +Q_STATIC_ASSERT((1 << Chunk::ChunkShift) == Chunk::ChunkSize); +Q_STATIC_ASSERT(1 << Chunk::SlotSizeShift == Chunk::SlotSize); +Q_STATIC_ASSERT(sizeof(HeapItem) == Chunk::SlotSize); +Q_STATIC_ASSERT(QT_POINTER_SIZE*8 == Chunk::Bits); +Q_STATIC_ASSERT((1 << Chunk::BitShift) == Chunk::Bits); + +} + +QT_END_NAMESPACE + +#endif |