/* -*- 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 "nsIObserver.h"
#include "nsIObserverService.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;
};

/**
 * nsExpirationTracker 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?
 */
template<class T, uint32_t K>
class nsExpirationTracker
{
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
   * AgeOneGeneration explicitly.
   */
  explicit nsExpirationTracker(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)");
    mObserver = new ExpirationTrackerObserver();
    mObserver->Init(this);
  }
  ~nsExpirationTracker()
  {
    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 AddObject(T* aObj)
  {
    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 = CheckStartTimer();
      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 RemoveObject(T* aObj)
  {
    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 MarkUsed(T* aObj)
  {
    nsExpirationState* state = aObj->GetExpirationState();
    if (mNewestGeneration == state->mGeneration) {
      return NS_OK;
    }
    RemoveObject(aObj);
    return AddObject(aObj);
  }

  /**
   * The timer calls this, but it can also be manually called if you want
   * to age objects "artifically". This can result in calls to NotifyExpired.
   */
  void AgeOneGeneration()
  {
    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 MarkUsed) inside NotifyExpired. 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;
      NotifyExpired(generation[index]);
    }
    // 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 AgeOneGeneration K times. Under normal circumstances this
   * will result in all objects getting NotifyExpired called on them, but
   * if NotifyExpired 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 AgeAllGenerations()
  {
    uint32_t i;
    for (i = 0; i < K; ++i) {
      AgeOneGeneration();
    }
  }

  class Iterator
  {
  private:
    nsExpirationTracker<T, K>* mTracker;
    uint32_t mGeneration;
    uint32_t mIndex;
  public:
    explicit Iterator(nsExpirationTracker<T, K>* aTracker)
      : 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 IsEmpty()
  {
    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 AgeOneGeneration
   * or AgeAllGenerations 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 NotifyExpired is called is K*(mTimerPeriod + D).
   *
   * The NotifyExpired call is expected to remove the object from the tracker,
   * but it need not. The object (or other objects) could be "resurrected"
   * by calling MarkUsed() 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 NotifyExpired(T* aObj) = 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 AgeAllGenerations()
   * to minimize memory usage.
   */
  class ExpirationTrackerObserver final : public nsIObserver
  {
  public:
    void Init(nsExpirationTracker<T, K>* 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:
    nsExpirationTracker<T, K>* mOwner;
  };

  static void TimerCallback(nsITimer* aTimer, void* aThis)
  {
    nsExpirationTracker* tracker = static_cast<nsExpirationTracker*>(aThis);
    tracker->AgeOneGeneration();
    // Cancel the timer if we have no objects to track
    if (tracker->IsEmpty()) {
      tracker->mTimer->Cancel();
      tracker->mTimer = nullptr;
    }
  }

  nsresult CheckStartTimer()
  {
    if (mTimer || !mTimerPeriod) {
      return NS_OK;
    }
    mTimer = do_CreateInstance("@mozilla.org/timer;1");
    if (!mTimer) {
      return NS_ERROR_OUT_OF_MEMORY;
    }
    mTimer->InitWithNamedFuncCallback(TimerCallback, this, mTimerPeriod,
                                      nsITimer::TYPE_REPEATING_SLACK, mName);
    return NS_OK;
  }
};

template<class T, uint32_t K>
NS_IMETHODIMP
nsExpirationTracker<T, K>::ExpirationTrackerObserver::Observe(
    nsISupports* aSubject, const char* aTopic, const char16_t* aData)
{
  if (!strcmp(aTopic, "memory-pressure") && mOwner) {
    mOwner->AgeAllGenerations();
  }
  return NS_OK;
}

template<class T, uint32_t K>
NS_IMETHODIMP_(MozExternalRefCountType)
nsExpirationTracker<T, K>::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>
NS_IMETHODIMP_(MozExternalRefCountType)
nsExpirationTracker<T, K>::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>
NS_IMETHODIMP
nsExpirationTracker<T, K>::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_*/