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