/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ /* vim: set ts=8 sts=2 et sw=2 tw=80: */ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ #ifndef NSEXPIRATIONTRACKER_H_ #define NSEXPIRATIONTRACKER_H_ #include "mozilla/Logging.h" #include "nsTArray.h" #include "nsITimer.h" #include "nsCOMPtr.h" #include "nsAutoPtr.h" #include "nsComponentManagerUtils.h" #include "nsIEventTarget.h" #include "nsIObserver.h" #include "nsIObserverService.h" #include "nsThreadUtils.h" #include "mozilla/Attributes.h" #include "mozilla/Services.h" /** * Data used to track the expiration state of an object. We promise that this * is 32 bits so that objects that includes this as a field can pad and align * efficiently. */ struct nsExpirationState { enum { NOT_TRACKED = (1U << 4) - 1, MAX_INDEX_IN_GENERATION = (1U << 28) - 1 }; nsExpirationState() : mGeneration(NOT_TRACKED) {} bool IsTracked() { return mGeneration != NOT_TRACKED; } /** * The generation that this object belongs to, or NOT_TRACKED. */ uint32_t mGeneration:4; uint32_t mIndexInGeneration:28; }; /** * ExpirationTracker classes: * - ExpirationTrackerImpl (Thread-safe class) * - nsExpirationTracker (Main-thread only class) * * These classes can track the lifetimes and usage of a large number of * objects, and send a notification some window of time after a live object was * last used. This is very useful when you manage a large number of objects * and want to flush some after they haven't been used for a while. * nsExpirationTracker is designed to be very space and time efficient. * * The type parameter T is the object type that we will track pointers to. T * must include an accessible method GetExpirationState() that returns a * pointer to an nsExpirationState associated with the object (preferably, * stored in a field of the object). * * The parameter K is the number of generations that will be used. Increasing * the number of generations narrows the window within which we promise * to fire notifications, at a slight increase in space cost for the tracker. * We require 2 <= K <= nsExpirationState::NOT_TRACKED (currently 15). * * To use this class, you need to inherit from it and override the * NotifyExpired() method. * * The approach is to track objects in K generations. When an object is accessed * it moves from its current generation to the newest generation. Generations * are stored in a cyclic array; when a timer interrupt fires, we advance * the current generation pointer to effectively age all objects very efficiently. * By storing information in each object about its generation and index within its * generation array, we make removal of objects from a generation very cheap. * * Future work: * -- Add a method to change the timer period? */ /** * Base class for ExiprationTracker implementations. * * nsExpirationTracker class below is a specialized class to be inherited by the * instances to be accessed only on main-thread. * * For creating a thread-safe tracker, you can define a subclass inheriting this * base class and specialize the Mutex and AutoLock to be used. * */ template<typename T, uint32_t K, typename Mutex, typename AutoLock> class ExpirationTrackerImpl { public: /** * Initialize the tracker. * @param aTimerPeriod the timer period in milliseconds. The guarantees * provided by the tracker are defined in terms of this period. If the * period is zero, then we don't use a timer and rely on someone calling * AgeOneGenerationLocked explicitly. */ ExpirationTrackerImpl(uint32_t aTimerPeriod, const char* aName) : mTimerPeriod(aTimerPeriod) , mNewestGeneration(0) , mInAgeOneGeneration(false) , mName(aName) { static_assert(K >= 2 && K <= nsExpirationState::NOT_TRACKED, "Unsupported number of generations (must be 2 <= K <= 15)"); MOZ_ASSERT(NS_IsMainThread()); mObserver = new ExpirationTrackerObserver(); mObserver->Init(this); } virtual ~ExpirationTrackerImpl() { MOZ_ASSERT(NS_IsMainThread()); if (mTimer) { mTimer->Cancel(); } mObserver->Destroy(); } /** * Add an object to be tracked. It must not already be tracked. It will * be added to the newest generation, i.e., as if it was just used. * @return an error on out-of-memory */ nsresult AddObjectLocked(T* aObj, const AutoLock& aAutoLock) { nsExpirationState* state = aObj->GetExpirationState(); NS_ASSERTION(!state->IsTracked(), "Tried to add an object that's already tracked"); nsTArray<T*>& generation = mGenerations[mNewestGeneration]; uint32_t index = generation.Length(); if (index > nsExpirationState::MAX_INDEX_IN_GENERATION) { NS_WARNING("More than 256M elements tracked, this is probably a problem"); return NS_ERROR_OUT_OF_MEMORY; } if (index == 0) { // We might need to start the timer nsresult rv = CheckStartTimerLocked(aAutoLock); if (NS_FAILED(rv)) { return rv; } } if (!generation.AppendElement(aObj)) { return NS_ERROR_OUT_OF_MEMORY; } state->mGeneration = mNewestGeneration; state->mIndexInGeneration = index; return NS_OK; } /** * Remove an object from the tracker. It must currently be tracked. */ void RemoveObjectLocked(T* aObj, const AutoLock& aAutoLock) { nsExpirationState* state = aObj->GetExpirationState(); NS_ASSERTION(state->IsTracked(), "Tried to remove an object that's not tracked"); nsTArray<T*>& generation = mGenerations[state->mGeneration]; uint32_t index = state->mIndexInGeneration; NS_ASSERTION(generation.Length() > index && generation[index] == aObj, "Object is lying about its index"); // Move the last object to fill the hole created by removing aObj uint32_t last = generation.Length() - 1; T* lastObj = generation[last]; generation[index] = lastObj; lastObj->GetExpirationState()->mIndexInGeneration = index; generation.RemoveElementAt(last); state->mGeneration = nsExpirationState::NOT_TRACKED; // We do not check whether we need to stop the timer here. The timer // will check that itself next time it fires. Checking here would not // be efficient since we'd need to track all generations. Also we could // thrash by incessantly creating and destroying timers if someone // kept adding and removing an object from the tracker. } /** * Notify that an object has been used. * @return an error if we lost the object from the tracker... */ nsresult MarkUsedLocked(T* aObj, const AutoLock& aAutoLock) { nsExpirationState* state = aObj->GetExpirationState(); if (mNewestGeneration == state->mGeneration) { return NS_OK; } RemoveObjectLocked(aObj, aAutoLock); return AddObjectLocked(aObj, aAutoLock); } /** * The timer calls this, but it can also be manually called if you want * to age objects "artifically". This can result in calls to NotifyExpiredLocked. */ void AgeOneGenerationLocked(const AutoLock& aAutoLock) { if (mInAgeOneGeneration) { NS_WARNING("Can't reenter AgeOneGeneration from NotifyExpired"); return; } mInAgeOneGeneration = true; uint32_t reapGeneration = mNewestGeneration > 0 ? mNewestGeneration - 1 : K - 1; nsTArray<T*>& generation = mGenerations[reapGeneration]; // The following is rather tricky. We have to cope with objects being // removed from this generation either because of a call to RemoveObject // (or indirectly via MarkUsedLocked) inside NotifyExpiredLocked. Fortunately // no objects can be added to this generation because it's not the newest // generation. We depend on the fact that RemoveObject can only cause // the indexes of objects in this generation to *decrease*, not increase. // So if we start from the end and work our way backwards we are guaranteed // to see each object at least once. size_t index = generation.Length(); for (;;) { // Objects could have been removed so index could be outside // the array index = XPCOM_MIN(index, generation.Length()); if (index == 0) { break; } --index; NotifyExpiredLocked(generation[index], aAutoLock); } // Any leftover objects from reapGeneration just end up in the new // newest-generation. This is bad form, though, so warn if there are any. if (!generation.IsEmpty()) { NS_WARNING("Expired objects were not removed or marked used"); } // Free excess memory used by the generation array, since we probably // just removed most or all of its elements. generation.Compact(); mNewestGeneration = reapGeneration; mInAgeOneGeneration = false; } /** * This just calls AgeOneGenerationLocked K times. Under normal circumstances * this will result in all objects getting NotifyExpiredLocked called on them, * but if NotifyExpiredLocked itself marks some objects as used, then those * objects might not expire. This would be a good thing to call if we get into * a critically-low memory situation. */ void AgeAllGenerationsLocked(const AutoLock& aAutoLock) { uint32_t i; for (i = 0; i < K; ++i) { AgeOneGenerationLocked(aAutoLock); } } class Iterator { private: ExpirationTrackerImpl<T, K, Mutex, AutoLock>* mTracker; uint32_t mGeneration; uint32_t mIndex; public: Iterator(ExpirationTrackerImpl<T, K, Mutex, AutoLock>* aTracker, AutoLock& aAutoLock) : mTracker(aTracker) , mGeneration(0) , mIndex(0) { } T* Next() { while (mGeneration < K) { nsTArray<T*>* generation = &mTracker->mGenerations[mGeneration]; if (mIndex < generation->Length()) { ++mIndex; return (*generation)[mIndex - 1]; } ++mGeneration; mIndex = 0; } return nullptr; } }; friend class Iterator; bool IsEmptyLocked(const AutoLock& aAutoLock) { for (uint32_t i = 0; i < K; ++i) { if (!mGenerations[i].IsEmpty()) { return false; } } return true; } protected: /** * This must be overridden to catch notifications. It is called whenever * we detect that an object has not been used for at least (K-1)*mTimerPeriod * milliseconds. If timer events are not delayed, it will be called within * roughly K*mTimerPeriod milliseconds after the last use. * (Unless AgeOneGenerationLocked or AgeAllGenerationsLocked have been called * to accelerate the aging process.) * * NOTE: These bounds ignore delays in timer firings due to actual work being * performed by the browser. We use a slack timer so there is always at least * mTimerPeriod milliseconds between firings, which gives us (K-1)*mTimerPeriod * as a pretty solid lower bound. The upper bound is rather loose, however. * If the maximum amount by which any given timer firing is delayed is D, then * the upper bound before NotifyExpiredLocked is called is K*(mTimerPeriod + D). * * The NotifyExpiredLocked call is expected to remove the object from the tracker, * but it need not. The object (or other objects) could be "resurrected" * by calling MarkUsedLocked() on them, or they might just not be removed. * Any objects left over that have not been resurrected or removed * are placed in the new newest-generation, but this is considered "bad form" * and should be avoided (we'll issue a warning). (This recycling counts * as "a use" for the purposes of the expiry guarantee above...) * * For robustness and simplicity, we allow objects to be notified more than * once here in the same timer tick. */ virtual void NotifyExpiredLocked(T*, const AutoLock&) = 0; virtual Mutex& GetMutex() = 0; private: class ExpirationTrackerObserver; RefPtr<ExpirationTrackerObserver> mObserver; nsTArray<T*> mGenerations[K]; nsCOMPtr<nsITimer> mTimer; uint32_t mTimerPeriod; uint32_t mNewestGeneration; bool mInAgeOneGeneration; const char* const mName; // Used for timer firing profiling. /** * Whenever "memory-pressure" is observed, it calls AgeAllGenerationsLocked() * to minimize memory usage. */ class ExpirationTrackerObserver final : public nsIObserver { public: void Init(ExpirationTrackerImpl<T, K, Mutex, AutoLock>* aObj) { mOwner = aObj; nsCOMPtr<nsIObserverService> obs = mozilla::services::GetObserverService(); if (obs) { obs->AddObserver(this, "memory-pressure", false); } } void Destroy() { mOwner = nullptr; nsCOMPtr<nsIObserverService> obs = mozilla::services::GetObserverService(); if (obs) { obs->RemoveObserver(this, "memory-pressure"); } } NS_DECL_ISUPPORTS NS_DECL_NSIOBSERVER private: ExpirationTrackerImpl<T, K, Mutex, AutoLock>* mOwner; }; void HandleLowMemory() { AutoLock lock(GetMutex()); AgeAllGenerationsLocked(lock); } void HandleTimeout() { AutoLock lock(GetMutex()); AgeOneGenerationLocked(lock); // Cancel the timer if we have no objects to track if (IsEmptyLocked(lock)) { mTimer->Cancel(); mTimer = nullptr; } } static void TimerCallback(nsITimer* aTimer, void* aThis) { ExpirationTrackerImpl* tracker = static_cast<ExpirationTrackerImpl*>(aThis); tracker->HandleTimeout(); } nsresult CheckStartTimerLocked(const AutoLock& aAutoLock) { if (mTimer || !mTimerPeriod) { return NS_OK; } mTimer = do_CreateInstance("@mozilla.org/timer;1"); if (!mTimer) { return NS_ERROR_OUT_OF_MEMORY; } if (!NS_IsMainThread()) { // TimerCallback should always be run on the main thread to prevent races // to the destruction of the tracker. nsCOMPtr<nsIEventTarget> target = do_GetMainThread(); NS_ENSURE_STATE(target); mTimer->SetTarget(target); } mTimer->InitWithNamedFuncCallback(TimerCallback, this, mTimerPeriod, nsITimer::TYPE_REPEATING_SLACK, mName); return NS_OK; } }; namespace detail { class PlaceholderLock { public: void Lock() {} void Unlock() {} }; class PlaceholderAutoLock { public: explicit PlaceholderAutoLock(PlaceholderLock&) { } ~PlaceholderAutoLock() = default; }; template<typename T, uint32_t K> using SingleThreadedExpirationTracker = ExpirationTrackerImpl<T, K, PlaceholderLock, PlaceholderAutoLock>; } // namespace detail template<typename T, uint32_t K> class nsExpirationTracker : protected ::detail::SingleThreadedExpirationTracker<T, K> { typedef ::detail::PlaceholderLock Lock; typedef ::detail::PlaceholderAutoLock AutoLock; Lock mLock; AutoLock FakeLock() { return AutoLock(mLock); } Lock& GetMutex() override { return mLock; } void NotifyExpiredLocked(T* aObject, const AutoLock&) override { NotifyExpired(aObject); } protected: virtual void NotifyExpired(T* aObj) = 0; public: nsExpirationTracker(uint32_t aTimerPeriod, const char* aName) : ::detail::SingleThreadedExpirationTracker<T, K>(aTimerPeriod, aName) { } virtual ~nsExpirationTracker() { } nsresult AddObject(T* aObj) { return this->AddObjectLocked(aObj, FakeLock()); } void RemoveObject(T* aObj) { this->RemoveObjectLocked(aObj, FakeLock()); } nsresult MarkUsed(T* aObj) { return this->MarkUsedLocked(aObj, FakeLock()); } void AgeOneGeneration() { this->AgeOneGenerationLocked(FakeLock()); } void AgeAllGenerations() { this->AgeAllGenerationsLocked(FakeLock()); } class Iterator { private: AutoLock mAutoLock; typename ExpirationTrackerImpl<T, K, Lock, AutoLock>::Iterator mIterator; public: explicit Iterator(nsExpirationTracker<T, K>* aTracker) : mAutoLock(aTracker->GetMutex()) , mIterator(aTracker, mAutoLock) { } T* Next() { return mIterator.Next(); } }; friend class Iterator; bool IsEmpty() { return this->IsEmptyLocked(FakeLock()); } }; template<typename T, uint32_t K, typename Mutex, typename AutoLock> NS_IMETHODIMP ExpirationTrackerImpl<T, K, Mutex, AutoLock>:: ExpirationTrackerObserver::Observe( nsISupports* aSubject, const char* aTopic, const char16_t* aData) { if (!strcmp(aTopic, "memory-pressure") && mOwner) { mOwner->HandleLowMemory(); } return NS_OK; } template<class T, uint32_t K, typename Mutex, typename AutoLock> NS_IMETHODIMP_(MozExternalRefCountType) ExpirationTrackerImpl<T, K, Mutex, AutoLock>:: ExpirationTrackerObserver::AddRef(void) { MOZ_ASSERT(int32_t(mRefCnt) >= 0, "illegal refcnt"); NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver); ++mRefCnt; NS_LOG_ADDREF(this, mRefCnt, "ExpirationTrackerObserver", sizeof(*this)); return mRefCnt; } template<class T, uint32_t K, typename Mutex, typename AutoLock> NS_IMETHODIMP_(MozExternalRefCountType) ExpirationTrackerImpl<T, K, Mutex, AutoLock>:: ExpirationTrackerObserver::Release(void) { MOZ_ASSERT(int32_t(mRefCnt) > 0, "dup release"); NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver); --mRefCnt; NS_LOG_RELEASE(this, mRefCnt, "ExpirationTrackerObserver"); if (mRefCnt == 0) { NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver); mRefCnt = 1; /* stabilize */ delete (this); return 0; } return mRefCnt; } template<class T, uint32_t K, typename Mutex, typename AutoLock> NS_IMETHODIMP ExpirationTrackerImpl<T, K, Mutex, AutoLock>:: ExpirationTrackerObserver::QueryInterface( REFNSIID aIID, void** aInstancePtr) { NS_ASSERTION(aInstancePtr, "QueryInterface requires a non-NULL destination!"); nsresult rv = NS_ERROR_FAILURE; NS_INTERFACE_TABLE(ExpirationTrackerObserver, nsIObserver) return rv; } #endif /*NSEXPIRATIONTRACKER_H_*/