diff options
Diffstat (limited to 'src/qml/memory/qv4mm.cpp')
-rw-r--r-- | src/qml/memory/qv4mm.cpp | 938 |
1 files changed, 581 insertions, 357 deletions
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 |