author | Michal Novotny <michal.novotny@gmail.com> |
Thu, 06 Oct 2016 11:23:52 +0200 | |
changeset 316798 | 86045bf00531d709031889f5fe27061ac8a522b6 |
parent 316797 | b508adb15d65a4e5cf535e987b1e0da8d6d7a77f |
child 316799 | 01bf91bcaeb2f2fa2123e8c2516568e569ef73d7 |
push id | 30783 |
push user | philringnalda@gmail.com |
push date | Fri, 07 Oct 2016 02:58:32 +0000 |
treeherder | mozilla-central@a5b04b518afe [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
reviewers | honzab |
bugs | 1249304 |
milestone | 52.0a1 |
first release with | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
last release without | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
--- a/netwerk/cache2/CacheIndex.cpp +++ b/netwerk/cache2/CacheIndex.cpp @@ -38,26 +38,39 @@ namespace mozilla { namespace net { namespace { class FrecencyComparator { public: bool Equals(CacheIndexRecord* a, CacheIndexRecord* b) const { + if (!a || !b) { + return false; + } + return a->mFrecency == b->mFrecency; } bool LessThan(CacheIndexRecord* a, CacheIndexRecord* b) const { - // Place entries with frecency 0 at the end of the array. + // Removed (=null) entries must be at the end of the array. + if (!a) { + return false; + } + if (!b) { + return true; + } + + // Place entries with frecency 0 at the end of the non-removed entries. if (a->mFrecency == 0) { return false; } if (b->mFrecency == 0) { return true; } + return a->mFrecency < b->mFrecency; } }; } // namespace /** * This helper class is responsible for keeping CacheIndex::mIndexStats and @@ -90,29 +103,49 @@ public: const CacheIndexEntry *entry = FindEntry(); mIndex->mIndexStats.AfterChange(entry); if (!entry || !entry->IsInitialized() || entry->IsRemoved()) { entry = nullptr; } if (entry && !mOldRecord) { - mIndex->InsertRecordToFrecencyArray(entry->mRec); + mIndex->mFrecencyArray.AppendRecord(entry->mRec); mIndex->AddRecordToIterators(entry->mRec); } else if (!entry && mOldRecord) { - mIndex->RemoveRecordFromFrecencyArray(mOldRecord); + mIndex->mFrecencyArray.RemoveRecord(mOldRecord); mIndex->RemoveRecordFromIterators(mOldRecord); } else if (entry && mOldRecord) { if (entry->mRec != mOldRecord) { // record has a different address, we have to replace it mIndex->ReplaceRecordInIterators(mOldRecord, entry->mRec); - mIndex->RemoveRecordFromFrecencyArray(mOldRecord); - mIndex->InsertRecordToFrecencyArray(entry->mRec); + + if (entry->mRec->mFrecency == mOldFrecency) { + // If frecency hasn't changed simply replace the pointer + mIndex->mFrecencyArray.ReplaceRecord(mOldRecord, entry->mRec); + } else { + // It is expected that when the frecency is changed the new value is + // always bigger than the old one. There is also a special case when + // we zero the frecency if eviction of the entry fails. If the above + // isn't true, this algorithm might not work properly and needs to be + // changed. + MOZ_ASSERT(entry->mRec->mFrecency == 0 || + entry->mRec->mFrecency > mOldFrecency); + + // Remove old pointer and insert the new one at the end of the array + mIndex->mFrecencyArray.RemoveRecord(mOldRecord); + mIndex->mFrecencyArray.AppendRecord(entry->mRec); + } } else if (entry->mRec->mFrecency != mOldFrecency) { - mIndex->mFrecencyArraySorted = false; + MOZ_ASSERT(entry->mRec->mFrecency == 0 || + entry->mRec->mFrecency > mOldFrecency); + + // Move the element at the end of the array + mIndex->mFrecencyArray.RemoveRecord(entry->mRec); + mIndex->mFrecencyArray.AppendRecord(entry->mRec); } } else { // both entries were removed or not initialized, do nothing } } // We cannot rely on nsTHashtable::GetEntry() in case we are removing entries // while iterating. Destructor is called before the entry is removed. Caller @@ -247,17 +280,16 @@ CacheIndex::CacheIndex() , mUpdateEventPending(false) , mSkipEntries(0) , mProcessEntries(0) , mRWBuf(nullptr) , mRWBufSize(0) , mRWBufPos(0) , mRWPending(false) , mJournalReadSuccessfully(false) - , mFrecencyArraySorted(false) , mAsyncGetDiskConsumptionBlocked(false) { sLock.AssertCurrentThreadOwns(); LOG(("CacheIndex::CacheIndex [this=%p]", this)); MOZ_COUNT_CTOR(CacheIndex); MOZ_ASSERT(!gInstance, "multiple CacheIndex instances!"); } @@ -1185,53 +1217,54 @@ CacheIndex::GetEntryForEviction(bool aIg if (!index) return NS_ERROR_NOT_INITIALIZED; if (!index->IsIndexUsable()) { return NS_ERROR_NOT_AVAILABLE; } SHA1Sum::Hash hash; - bool foundEntry = false; - uint32_t i; + CacheIndexRecord *foundRecord = nullptr; + uint32_t skipped = 0; // find first non-forced valid and unpinned entry with the lowest frecency - if (!index->mFrecencyArraySorted) { - index->mFrecencyArray.Sort(FrecencyComparator()); - index->mFrecencyArraySorted = true; - } - - for (i = 0; i < index->mFrecencyArray.Length(); ++i) { - memcpy(&hash, &index->mFrecencyArray[i]->mHash, sizeof(SHA1Sum::Hash)); + index->mFrecencyArray.SortIfNeeded(); + + for (auto iter = index->mFrecencyArray.Iter(); !iter.Done(); iter.Next()) { + CacheIndexRecord *rec = iter.Get(); + + memcpy(&hash, rec->mHash, sizeof(SHA1Sum::Hash)); + + ++skipped; if (IsForcedValidEntry(&hash)) { continue; } - if (CacheIndexEntry::IsPinned(index->mFrecencyArray[i])) { + if (CacheIndexEntry::IsPinned(rec)) { continue; } - if (aIgnoreEmptyEntries && - !CacheIndexEntry::GetFileSize(index->mFrecencyArray[i])) { + if (aIgnoreEmptyEntries && !CacheIndexEntry::GetFileSize(rec)) { continue; } - foundEntry = true; + --skipped; + foundRecord = rec; break; } - if (!foundEntry) + if (!foundRecord) return NS_ERROR_NOT_AVAILABLE; - *aCnt = index->mFrecencyArray.Length() - i; + *aCnt = skipped; LOG(("CacheIndex::GetEntryForEviction() - returning entry from frecency " "array [hash=%08x%08x%08x%08x%08x, cnt=%u, frecency=%u]", - LOGSHA1(&hash), *aCnt, index->mFrecencyArray[i]->mFrecency)); + LOGSHA1(&hash), *aCnt, foundRecord->mFrecency)); memcpy(aHash, &hash, sizeof(SHA1Sum::Hash)); return NS_OK; } // static @@ -1315,18 +1348,18 @@ CacheIndex::GetCacheStats(nsILoadContext if (!aInfo) { return NS_ERROR_INVALID_ARG; } *aSize = 0; *aCount = 0; - for (uint32_t i = 0; i < index->mFrecencyArray.Length(); ++i) { - CacheIndexRecord* record = index->mFrecencyArray[i]; + for (auto iter = index->mFrecencyArray.Iter(); !iter.Done(); iter.Next()) { + CacheIndexRecord *record = iter.Get(); if (!CacheIndexEntry::RecordMatchesLoadContextInfo(record, aInfo)) continue; *aSize += CacheIndexEntry::GetFileSize(record); ++*aCount; } return NS_OK; @@ -1399,32 +1432,31 @@ CacheIndex::GetIterator(nsILoadContextIn if (!index) { return NS_ERROR_NOT_INITIALIZED; } if (!index->IsIndexUsable()) { return NS_ERROR_NOT_AVAILABLE; } - RefPtr<CacheIndexIterator> iter; + RefPtr<CacheIndexIterator> idxIter; if (aInfo) { - iter = new CacheIndexContextIterator(index, aAddNew, aInfo); + idxIter = new CacheIndexContextIterator(index, aAddNew, aInfo); } else { - iter = new CacheIndexIterator(index, aAddNew); + idxIter = new CacheIndexIterator(index, aAddNew); } - if (!index->mFrecencyArraySorted) { - index->mFrecencyArray.Sort(FrecencyComparator()); - index->mFrecencyArraySorted = true; + index->mFrecencyArray.SortIfNeeded(); + + for (auto iter = index->mFrecencyArray.Iter(); !iter.Done(); iter.Next()) { + idxIter->AddRecord(iter.Get()); } - iter->AddRecords(index->mFrecencyArray); - - index->mIterators.AppendElement(iter); - iter.swap(*_retval); + index->mIterators.AppendElement(idxIter); + idxIter.swap(*_retval); return NS_OK; } // static nsresult CacheIndex::IsUpToDate(bool *_retval) { LOG(("CacheIndex::IsUpToDate()")); @@ -3226,34 +3258,90 @@ CacheIndex::ReleaseBuffer() free(mRWBuf); mRWBuf = nullptr; mRWBufSize = 0; mRWBufPos = 0; } void -CacheIndex::InsertRecordToFrecencyArray(CacheIndexRecord *aRecord) +CacheIndex::FrecencyArray::AppendRecord(CacheIndexRecord *aRecord) { - LOG(("CacheIndex::InsertRecordToFrecencyArray() [record=%p, hash=%08x%08x%08x" + LOG(("CacheIndex::FrecencyArray::AppendRecord() [record=%p, hash=%08x%08x%08x" "%08x%08x]", aRecord, LOGSHA1(aRecord->mHash))); - MOZ_ASSERT(!mFrecencyArray.Contains(aRecord)); - mFrecencyArray.AppendElement(aRecord); - mFrecencyArraySorted = false; + MOZ_ASSERT(!mRecs.Contains(aRecord)); + mRecs.AppendElement(aRecord); + + // If the new frecency is 0, the element should be at the end of the array, + // i.e. this change doesn't affect order of the array + if (aRecord->mFrecency != 0) { + ++mUnsortedElements; + } +} + +void +CacheIndex::FrecencyArray::RemoveRecord(CacheIndexRecord *aRecord) +{ + LOG(("CacheIndex::FrecencyArray::RemoveRecord() [record=%p]", aRecord)); + + decltype(mRecs)::index_type idx; + idx = mRecs.IndexOf(aRecord); + MOZ_RELEASE_ASSERT(idx != mRecs.NoIndex); + mRecs[idx] = nullptr; + ++mRemovedElements; + + // Calling SortIfNeeded ensures that we get rid of removed elements in the + // array once we hit the limit. + SortIfNeeded(); } void -CacheIndex::RemoveRecordFromFrecencyArray(CacheIndexRecord *aRecord) +CacheIndex::FrecencyArray::ReplaceRecord(CacheIndexRecord *aOldRecord, + CacheIndexRecord *aNewRecord) +{ + LOG(("CacheIndex::FrecencyArray::ReplaceRecord() [oldRecord=%p, " + "newRecord=%p]", aOldRecord, aNewRecord)); + + decltype(mRecs)::index_type idx; + idx = mRecs.IndexOf(aOldRecord); + MOZ_RELEASE_ASSERT(idx != mRecs.NoIndex); + mRecs[idx] = aNewRecord; +} + +void +CacheIndex::FrecencyArray::SortIfNeeded() { - LOG(("CacheIndex::RemoveRecordFromFrecencyArray() [record=%p]", aRecord)); - - DebugOnly<bool> removed; - removed = mFrecencyArray.RemoveElement(aRecord); - MOZ_ASSERT(removed); + const uint32_t kMaxUnsortedCount = 512; + const uint32_t kMaxUnsortedPercent = 10; + const uint32_t kMaxRemovedCount = 512; + + uint32_t unsortedLimit = + std::min<uint32_t>(kMaxUnsortedCount, Length() * kMaxUnsortedPercent / 100); + + if (mUnsortedElements > unsortedLimit || + mRemovedElements > kMaxRemovedCount) { + LOG(("CacheIndex::FrecencyArray::SortIfNeeded() - Sorting array " + "[unsortedElements=%u, unsortedLimit=%u, removedElements=%u, " + "maxRemovedCount=%u]", mUnsortedElements, unsortedLimit, + mRemovedElements, kMaxRemovedCount)); + + mRecs.Sort(FrecencyComparator()); + mUnsortedElements = 0; + if (mRemovedElements) { +#ifdef DEBUG + for (uint32_t i = Length(); i < mRecs.Length(); ++i) { + MOZ_ASSERT(!mRecs[i]); + } +#endif + // Removed elements are at the end after sorting. + mRecs.RemoveElementsAt(Length(), mRemovedElements); + mRemovedElements = 0; + } + } } void CacheIndex::AddRecordToIterators(CacheIndexRecord *aRecord) { sLock.AssertCurrentThreadOwns(); for (uint32_t i = 0; i < mIterators.Length(); ++i) { @@ -3621,17 +3709,17 @@ CacheIndex::SizeOfExcludingThisInternal( n += mallocSizeOf(mRWBuf); n += mallocSizeOf(mRWHash); n += mIndex.SizeOfExcludingThis(mallocSizeOf); n += mPendingUpdates.SizeOfExcludingThis(mallocSizeOf); n += mTmpJournal.SizeOfExcludingThis(mallocSizeOf); // mFrecencyArray items are reported by mIndex/mPendingUpdates - n += mFrecencyArray.ShallowSizeOfExcludingThis(mallocSizeOf); + n += mFrecencyArray.mRecs.ShallowSizeOfExcludingThis(mallocSizeOf); n += mDiskConsumptionObservers.ShallowSizeOfExcludingThis(mallocSizeOf); return n; } // static size_t CacheIndex::SizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) @@ -3705,17 +3793,19 @@ void CacheIndex::ReportHashStats() { // We're gathering the hash stats only once, exclude too small caches. if (CacheObserver::HashStatsReported() || mFrecencyArray.Length() < 15000) { return; } nsTArray<CacheIndexRecord *> records; - records.AppendElements(mFrecencyArray); + for (auto iter = mFrecencyArray.Iter(); !iter.Done(); iter.Next()) { + records.AppendElement(iter.Get()); + } records.Sort(HashComparator()); for (uint32_t i = 1; i < records.Length(); i++) { ReportHashSizeMatch(&records[i-1]->mHash, &records[i]->mHash); } CacheObserver::SetHashStatsReported();
--- a/netwerk/cache2/CacheIndex.h +++ b/netwerk/cache2/CacheIndex.h @@ -916,20 +916,16 @@ private: static char const * StateString(EState aState); void ChangeState(EState aNewState); void NotifyAsyncGetDiskConsumptionCallbacks(); // Allocates and releases buffer used for reading and writing index. void AllocBuffer(); void ReleaseBuffer(); - // Methods used by CacheIndexEntryAutoManage to keep the arrays up to date. - void InsertRecordToFrecencyArray(CacheIndexRecord *aRecord); - void RemoveRecordFromFrecencyArray(CacheIndexRecord *aRecord); - // Methods used by CacheIndexEntryAutoManage to keep the iterators up to date. void AddRecordToIterators(CacheIndexRecord *aRecord); void RemoveRecordFromIterators(CacheIndexRecord *aRecord); void ReplaceRecordInIterators(CacheIndexRecord *aOldRecord, CacheIndexRecord *aNewRecord); // Memory reporting (private part) size_t SizeOfExcludingThisInternal(mozilla::MallocSizeOf mallocSizeOf) const; @@ -1026,22 +1022,89 @@ private: CacheIndexStats mIndexStats; // When reading journal, we must first parse the whole file and apply the // changes iff the journal was read successfully. mTmpJournal is used to store // entries from the journal file. We throw away all these entries if parsing // of the journal fails or the hash does not match. nsTHashtable<CacheIndexEntry> mTmpJournal; - // An array that keeps entry records ordered by eviction preference; we take - // the entry with lowest valid frecency. Zero frecency is an initial value - // and such entries are stored at the end of the array. Uninitialized entries - // and entries marked as deleted are not present in this array. - nsTArray<CacheIndexRecord *> mFrecencyArray; - bool mFrecencyArraySorted; + // FrecencyArray maintains order of entry records for eviction. Ideally, the + // records would be ordered by frecency all the time, but since this would be + // quite expensive, we allow certain amount of entries to be out of order. + // When the frecency is updated the new value is always bigger than the old + // one. Instead of keeping updated entries at the same position, we move them + // at the end of the array. This protects recently updated entries from + // eviction. The array is sorted once we hit the limit of maximum unsorted + // entries. + class FrecencyArray + { + class Iterator + { + public: + explicit Iterator(nsTArray<CacheIndexRecord *> *aRecs) + : mRecs(aRecs) + , mIdx(0) + { + while (!Done() && !(*mRecs)[mIdx]) { + mIdx++; + } + } + + bool Done() const { return mIdx == mRecs->Length(); } + + CacheIndexRecord* Get() const + { + MOZ_ASSERT(!Done()); + return (*mRecs)[mIdx]; + } + + void Next() + { + MOZ_ASSERT(!Done()); + ++mIdx; + while (!Done() && !(*mRecs)[mIdx]) { + mIdx++; + } + } + + private: + nsTArray<CacheIndexRecord *> *mRecs; + uint32_t mIdx; + }; + + public: + Iterator Iter() { return Iterator(&mRecs); } + + FrecencyArray() : mUnsortedElements(0) + , mRemovedElements(0) {} + + // Methods used by CacheIndexEntryAutoManage to keep the array up to date. + void AppendRecord(CacheIndexRecord *aRecord); + void RemoveRecord(CacheIndexRecord *aRecord); + void ReplaceRecord(CacheIndexRecord *aOldRecord, + CacheIndexRecord *aNewRecord); + void SortIfNeeded(); + + size_t Length() const { return mRecs.Length() - mRemovedElements; } + void Clear() { mRecs.Clear(); } + + private: + friend class CacheIndex; + + nsTArray<CacheIndexRecord *> mRecs; + uint32_t mUnsortedElements; + // Instead of removing elements from the array immediately, we null them out + // and the iterator skips them when accessing the array. The null pointers + // are placed at the end during sorting and we strip them out all at once. + // This saves moving a lot of memory in nsTArray::RemoveElementsAt. + uint32_t mRemovedElements; + }; + + FrecencyArray mFrecencyArray; nsTArray<CacheIndexIterator *> mIterators; // This flag is true iff we are between CacheStorageService:Clear() and processing // all contexts to be evicted. It will make UI to show "calculating" instead of // any intermediate cache size. bool mAsyncGetDiskConsumptionBlocked;
--- a/netwerk/cache2/CacheIndexIterator.cpp +++ b/netwerk/cache2/CacheIndexIterator.cpp @@ -85,24 +85,16 @@ CacheIndexIterator::CloseInternal(nsresu void CacheIndexIterator::AddRecord(CacheIndexRecord *aRecord) { LOG(("CacheIndexIterator::AddRecord() [this=%p, record=%p]", this, aRecord)); mRecords.AppendElement(aRecord); } -void -CacheIndexIterator::AddRecords(const nsTArray<CacheIndexRecord *> &aRecords) -{ - LOG(("CacheIndexIterator::AddRecords() [this=%p]", this)); - - mRecords.AppendElements(aRecords); -} - bool CacheIndexIterator::RemoveRecord(CacheIndexRecord *aRecord) { LOG(("CacheIndexIterator::RemoveRecord() [this=%p, record=%p]", this, aRecord)); return mRecords.RemoveElement(aRecord); }
--- a/netwerk/cache2/CacheIndexIterator.h +++ b/netwerk/cache2/CacheIndexIterator.h @@ -38,17 +38,16 @@ public: protected: friend class CacheIndex; nsresult CloseInternal(nsresult aStatus); bool ShouldBeNewAdded() { return mAddNew; } virtual void AddRecord(CacheIndexRecord *aRecord); - virtual void AddRecords(const nsTArray<CacheIndexRecord *> &aRecords); bool RemoveRecord(CacheIndexRecord *aRecord); bool ReplaceRecord(CacheIndexRecord *aOldRecord, CacheIndexRecord *aNewRecord); nsresult mStatus; RefPtr<CacheIndex> mIndex; nsTArray<CacheIndexRecord *> mRecords; bool mAddNew;