1 files changed, 570 insertions, 0 deletions
diff --git a/xpcom/ds/nsExpirationTracker.h b/xpcom/ds/nsExpirationTracker.h
new file mode 100644
index 000000000..2e77895db
--- /dev/null
+++ b/xpcom/ds/nsExpirationTracker.h
@@ -0,0 +1,570 @@
+/* -*- 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_*/