1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/ds/nsExpirationTracker.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,383 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#ifndef NSEXPIRATIONTRACKER_H_
1.10 +#define NSEXPIRATIONTRACKER_H_
1.11 +
1.12 +#include "mozilla/Attributes.h"
1.13 +
1.14 +#include "prlog.h"
1.15 +#include "nsTArray.h"
1.16 +#include "nsITimer.h"
1.17 +#include "nsCOMPtr.h"
1.18 +#include "nsAutoPtr.h"
1.19 +#include "nsComponentManagerUtils.h"
1.20 +#include "nsIObserver.h"
1.21 +#include "nsIObserverService.h"
1.22 +#include "mozilla/Services.h"
1.23 +#include "mozilla/Attributes.h"
1.24 +
1.25 +/**
1.26 + * Data used to track the expiration state of an object. We promise that this
1.27 + * is 32 bits so that objects that includes this as a field can pad and align
1.28 + * efficiently.
1.29 + */
1.30 +struct nsExpirationState {
1.31 + enum { NOT_TRACKED = (1U << 4) - 1,
1.32 + MAX_INDEX_IN_GENERATION = (1U << 28) - 1 };
1.33 +
1.34 + nsExpirationState() : mGeneration(NOT_TRACKED) {}
1.35 + bool IsTracked() { return mGeneration != NOT_TRACKED; }
1.36 +
1.37 + /**
1.38 + * The generation that this object belongs to, or NOT_TRACKED.
1.39 + */
1.40 + uint32_t mGeneration:4;
1.41 + uint32_t mIndexInGeneration:28;
1.42 +};
1.43 +
1.44 +/**
1.45 + * nsExpirationTracker can track the lifetimes and usage of a large number of
1.46 + * objects, and send a notification some window of time after a live object was
1.47 + * last used. This is very useful when you manage a large number of objects
1.48 + * and want to flush some after they haven't been used for a while.
1.49 + * nsExpirationTracker is designed to be very space and time efficient.
1.50 + *
1.51 + * The type parameter T is the object type that we will track pointers to. T
1.52 + * must include an accessible method GetExpirationState() that returns a
1.53 + * pointer to an nsExpirationState associated with the object (preferably,
1.54 + * stored in a field of the object).
1.55 + *
1.56 + * The parameter K is the number of generations that will be used. Increasing
1.57 + * the number of generations narrows the window within which we promise
1.58 + * to fire notifications, at a slight increase in space cost for the tracker.
1.59 + * We require 2 <= K <= nsExpirationState::NOT_TRACKED (currently 15).
1.60 + *
1.61 + * To use this class, you need to inherit from it and override the
1.62 + * NotifyExpired() method.
1.63 + *
1.64 + * The approach is to track objects in K generations. When an object is accessed
1.65 + * it moves from its current generation to the newest generation. Generations
1.66 + * are stored in a cyclic array; when a timer interrupt fires, we advance
1.67 + * the current generation pointer to effectively age all objects very efficiently.
1.68 + * By storing information in each object about its generation and index within its
1.69 + * generation array, we make removal of objects from a generation very cheap.
1.70 + *
1.71 + * Future work:
1.72 + * -- Add a method to change the timer period?
1.73 + */
1.74 +template <class T, uint32_t K> class nsExpirationTracker {
1.75 + public:
1.76 + /**
1.77 + * Initialize the tracker.
1.78 + * @param aTimerPeriod the timer period in milliseconds. The guarantees
1.79 + * provided by the tracker are defined in terms of this period. If the
1.80 + * period is zero, then we don't use a timer and rely on someone calling
1.81 + * AgeOneGeneration explicitly.
1.82 + */
1.83 + nsExpirationTracker(uint32_t aTimerPeriod)
1.84 + : mTimerPeriod(aTimerPeriod), mNewestGeneration(0),
1.85 + mInAgeOneGeneration(false) {
1.86 + static_assert(K >= 2 && K <= nsExpirationState::NOT_TRACKED,
1.87 + "Unsupported number of generations (must be 2 <= K <= 15)");
1.88 + mObserver = new ExpirationTrackerObserver();
1.89 + mObserver->Init(this);
1.90 + }
1.91 + ~nsExpirationTracker() {
1.92 + if (mTimer) {
1.93 + mTimer->Cancel();
1.94 + }
1.95 + mObserver->Destroy();
1.96 + }
1.97 +
1.98 + /**
1.99 + * Add an object to be tracked. It must not already be tracked. It will
1.100 + * be added to the newest generation, i.e., as if it was just used.
1.101 + * @return an error on out-of-memory
1.102 + */
1.103 + nsresult AddObject(T* aObj) {
1.104 + nsExpirationState* state = aObj->GetExpirationState();
1.105 + NS_ASSERTION(!state->IsTracked(), "Tried to add an object that's already tracked");
1.106 + nsTArray<T*>& generation = mGenerations[mNewestGeneration];
1.107 + uint32_t index = generation.Length();
1.108 + if (index > nsExpirationState::MAX_INDEX_IN_GENERATION) {
1.109 + NS_WARNING("More than 256M elements tracked, this is probably a problem");
1.110 + return NS_ERROR_OUT_OF_MEMORY;
1.111 + }
1.112 + if (index == 0) {
1.113 + // We might need to start the timer
1.114 + nsresult rv = CheckStartTimer();
1.115 + if (NS_FAILED(rv))
1.116 + return rv;
1.117 + }
1.118 + if (!generation.AppendElement(aObj))
1.119 + return NS_ERROR_OUT_OF_MEMORY;
1.120 + state->mGeneration = mNewestGeneration;
1.121 + state->mIndexInGeneration = index;
1.122 + return NS_OK;
1.123 + }
1.124 +
1.125 + /**
1.126 + * Remove an object from the tracker. It must currently be tracked.
1.127 + */
1.128 + void RemoveObject(T* aObj) {
1.129 + nsExpirationState* state = aObj->GetExpirationState();
1.130 + NS_ASSERTION(state->IsTracked(), "Tried to remove an object that's not tracked");
1.131 + nsTArray<T*>& generation = mGenerations[state->mGeneration];
1.132 + uint32_t index = state->mIndexInGeneration;
1.133 + NS_ASSERTION(generation.Length() > index &&
1.134 + generation[index] == aObj, "Object is lying about its index");
1.135 + // Move the last object to fill the hole created by removing aObj
1.136 + uint32_t last = generation.Length() - 1;
1.137 + T* lastObj = generation[last];
1.138 + generation[index] = lastObj;
1.139 + lastObj->GetExpirationState()->mIndexInGeneration = index;
1.140 + generation.RemoveElementAt(last);
1.141 + state->mGeneration = nsExpirationState::NOT_TRACKED;
1.142 + // We do not check whether we need to stop the timer here. The timer
1.143 + // will check that itself next time it fires. Checking here would not
1.144 + // be efficient since we'd need to track all generations. Also we could
1.145 + // thrash by incessantly creating and destroying timers if someone
1.146 + // kept adding and removing an object from the tracker.
1.147 + }
1.148 +
1.149 + /**
1.150 + * Notify that an object has been used.
1.151 + * @return an error if we lost the object from the tracker...
1.152 + */
1.153 + nsresult MarkUsed(T* aObj) {
1.154 + nsExpirationState* state = aObj->GetExpirationState();
1.155 + if (mNewestGeneration == state->mGeneration)
1.156 + return NS_OK;
1.157 + RemoveObject(aObj);
1.158 + return AddObject(aObj);
1.159 + }
1.160 +
1.161 + /**
1.162 + * The timer calls this, but it can also be manually called if you want
1.163 + * to age objects "artifically". This can result in calls to NotifyExpired.
1.164 + */
1.165 + void AgeOneGeneration() {
1.166 + if (mInAgeOneGeneration) {
1.167 + NS_WARNING("Can't reenter AgeOneGeneration from NotifyExpired");
1.168 + return;
1.169 + }
1.170 +
1.171 + mInAgeOneGeneration = true;
1.172 + uint32_t reapGeneration =
1.173 + mNewestGeneration > 0 ? mNewestGeneration - 1 : K - 1;
1.174 + nsTArray<T*>& generation = mGenerations[reapGeneration];
1.175 + // The following is rather tricky. We have to cope with objects being
1.176 + // removed from this generation either because of a call to RemoveObject
1.177 + // (or indirectly via MarkUsed) inside NotifyExpired. Fortunately no
1.178 + // objects can be added to this generation because it's not the newest
1.179 + // generation. We depend on the fact that RemoveObject can only cause
1.180 + // the indexes of objects in this generation to *decrease*, not increase.
1.181 + // So if we start from the end and work our way backwards we are guaranteed
1.182 + // to see each object at least once.
1.183 + uint32_t index = generation.Length();
1.184 + for (;;) {
1.185 + // Objects could have been removed so index could be outside
1.186 + // the array
1.187 + index = XPCOM_MIN(index, generation.Length());
1.188 + if (index == 0)
1.189 + break;
1.190 + --index;
1.191 + NotifyExpired(generation[index]);
1.192 + }
1.193 + // Any leftover objects from reapGeneration just end up in the new
1.194 + // newest-generation. This is bad form, though, so warn if there are any.
1.195 + if (!generation.IsEmpty()) {
1.196 + NS_WARNING("Expired objects were not removed or marked used");
1.197 + }
1.198 + // Free excess memory used by the generation array, since we probably
1.199 + // just removed most or all of its elements.
1.200 + generation.Compact();
1.201 + mNewestGeneration = reapGeneration;
1.202 + mInAgeOneGeneration = false;
1.203 + }
1.204 +
1.205 + /**
1.206 + * This just calls AgeOneGeneration K times. Under normal circumstances this
1.207 + * will result in all objects getting NotifyExpired called on them, but
1.208 + * if NotifyExpired itself marks some objects as used, then those objects
1.209 + * might not expire. This would be a good thing to call if we get into
1.210 + * a critically-low memory situation.
1.211 + */
1.212 + void AgeAllGenerations() {
1.213 + uint32_t i;
1.214 + for (i = 0; i < K; ++i) {
1.215 + AgeOneGeneration();
1.216 + }
1.217 + }
1.218 +
1.219 + class Iterator {
1.220 + private:
1.221 + nsExpirationTracker<T,K>* mTracker;
1.222 + uint32_t mGeneration;
1.223 + uint32_t mIndex;
1.224 + public:
1.225 + Iterator(nsExpirationTracker<T,K>* aTracker)
1.226 + : mTracker(aTracker), mGeneration(0), mIndex(0) {}
1.227 + T* Next() {
1.228 + while (mGeneration < K) {
1.229 + nsTArray<T*>* generation = &mTracker->mGenerations[mGeneration];
1.230 + if (mIndex < generation->Length()) {
1.231 + ++mIndex;
1.232 + return (*generation)[mIndex - 1];
1.233 + }
1.234 + ++mGeneration;
1.235 + mIndex = 0;
1.236 + }
1.237 + return nullptr;
1.238 + }
1.239 + };
1.240 +
1.241 + friend class Iterator;
1.242 +
1.243 + bool IsEmpty() {
1.244 + for (uint32_t i = 0; i < K; ++i) {
1.245 + if (!mGenerations[i].IsEmpty())
1.246 + return false;
1.247 + }
1.248 + return true;
1.249 + }
1.250 +
1.251 + protected:
1.252 + /**
1.253 + * This must be overridden to catch notifications. It is called whenever
1.254 + * we detect that an object has not been used for at least (K-1)*mTimerPeriod
1.255 + * milliseconds. If timer events are not delayed, it will be called within
1.256 + * roughly K*mTimerPeriod milliseconds after the last use. (Unless AgeOneGeneration
1.257 + * or AgeAllGenerations have been called to accelerate the aging process.)
1.258 + *
1.259 + * NOTE: These bounds ignore delays in timer firings due to actual work being
1.260 + * performed by the browser. We use a slack timer so there is always at least
1.261 + * mTimerPeriod milliseconds between firings, which gives us (K-1)*mTimerPeriod
1.262 + * as a pretty solid lower bound. The upper bound is rather loose, however.
1.263 + * If the maximum amount by which any given timer firing is delayed is D, then
1.264 + * the upper bound before NotifyExpired is called is K*(mTimerPeriod + D).
1.265 + *
1.266 + * The NotifyExpired call is expected to remove the object from the tracker,
1.267 + * but it need not. The object (or other objects) could be "resurrected"
1.268 + * by calling MarkUsed() on them, or they might just not be removed.
1.269 + * Any objects left over that have not been resurrected or removed
1.270 + * are placed in the new newest-generation, but this is considered "bad form"
1.271 + * and should be avoided (we'll issue a warning). (This recycling counts
1.272 + * as "a use" for the purposes of the expiry guarantee above...)
1.273 + *
1.274 + * For robustness and simplicity, we allow objects to be notified more than
1.275 + * once here in the same timer tick.
1.276 + */
1.277 + virtual void NotifyExpired(T* aObj) = 0;
1.278 +
1.279 + private:
1.280 + class ExpirationTrackerObserver;
1.281 + nsRefPtr<ExpirationTrackerObserver> mObserver;
1.282 + nsTArray<T*> mGenerations[K];
1.283 + nsCOMPtr<nsITimer> mTimer;
1.284 + uint32_t mTimerPeriod;
1.285 + uint32_t mNewestGeneration;
1.286 + bool mInAgeOneGeneration;
1.287 +
1.288 + /**
1.289 + * Whenever "memory-pressure" is observed, it calls AgeAllGenerations()
1.290 + * to minimize memory usage.
1.291 + */
1.292 + class ExpirationTrackerObserver MOZ_FINAL : public nsIObserver {
1.293 + public:
1.294 + void Init(nsExpirationTracker<T,K> *obj) {
1.295 + mOwner = obj;
1.296 + nsCOMPtr<nsIObserverService> obs = mozilla::services::GetObserverService();
1.297 + if (obs) {
1.298 + obs->AddObserver(this, "memory-pressure", false);
1.299 + }
1.300 + }
1.301 + void Destroy() {
1.302 + mOwner = nullptr;
1.303 + nsCOMPtr<nsIObserverService> obs = mozilla::services::GetObserverService();
1.304 + if (obs)
1.305 + obs->RemoveObserver(this, "memory-pressure");
1.306 + }
1.307 + NS_DECL_ISUPPORTS
1.308 + NS_DECL_NSIOBSERVER
1.309 + private:
1.310 + nsExpirationTracker<T,K> *mOwner;
1.311 + };
1.312 +
1.313 + static void TimerCallback(nsITimer* aTimer, void* aThis) {
1.314 + nsExpirationTracker* tracker = static_cast<nsExpirationTracker*>(aThis);
1.315 + tracker->AgeOneGeneration();
1.316 + // Cancel the timer if we have no objects to track
1.317 + if (tracker->IsEmpty()) {
1.318 + tracker->mTimer->Cancel();
1.319 + tracker->mTimer = nullptr;
1.320 + }
1.321 + }
1.322 +
1.323 + nsresult CheckStartTimer() {
1.324 + if (mTimer || !mTimerPeriod)
1.325 + return NS_OK;
1.326 + mTimer = do_CreateInstance("@mozilla.org/timer;1");
1.327 + if (!mTimer)
1.328 + return NS_ERROR_OUT_OF_MEMORY;
1.329 + mTimer->InitWithFuncCallback(TimerCallback, this, mTimerPeriod,
1.330 + nsITimer::TYPE_REPEATING_SLACK);
1.331 + return NS_OK;
1.332 + }
1.333 +};
1.334 +
1.335 +template<class T, uint32_t K>
1.336 +NS_IMETHODIMP
1.337 +nsExpirationTracker<T, K>::ExpirationTrackerObserver::Observe(nsISupports *aSubject,
1.338 + const char *aTopic,
1.339 + const char16_t *aData)
1.340 +{
1.341 + if (!strcmp(aTopic, "memory-pressure") && mOwner)
1.342 + mOwner->AgeAllGenerations();
1.343 + return NS_OK;
1.344 +}
1.345 +
1.346 +template <class T, uint32_t K>
1.347 +NS_IMETHODIMP_(MozExternalRefCountType)
1.348 +nsExpirationTracker<T,K>::ExpirationTrackerObserver::AddRef(void)
1.349 +{
1.350 + MOZ_ASSERT(int32_t(mRefCnt) >= 0, "illegal refcnt");
1.351 + NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver);
1.352 + ++mRefCnt;
1.353 + NS_LOG_ADDREF(this, mRefCnt, "ExpirationTrackerObserver", sizeof(*this));
1.354 + return mRefCnt;
1.355 +}
1.356 +
1.357 +template <class T, uint32_t K>
1.358 +NS_IMETHODIMP_(MozExternalRefCountType)
1.359 +nsExpirationTracker<T,K>::ExpirationTrackerObserver::Release(void)
1.360 +{
1.361 + MOZ_ASSERT(int32_t(mRefCnt) > 0, "dup release");
1.362 + NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver);
1.363 + --mRefCnt;
1.364 + NS_LOG_RELEASE(this, mRefCnt, "ExpirationTrackerObserver");
1.365 + if (mRefCnt == 0) {
1.366 + NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver);
1.367 + mRefCnt = 1; /* stabilize */
1.368 + delete (this);
1.369 + return 0;
1.370 + }
1.371 + return mRefCnt;
1.372 +}
1.373 +
1.374 +template <class T, uint32_t K>
1.375 +NS_IMETHODIMP
1.376 +nsExpirationTracker<T,K>::ExpirationTrackerObserver::QueryInterface(REFNSIID aIID,
1.377 + void** aInstancePtr)
1.378 +{
1.379 + NS_ASSERTION(aInstancePtr,
1.380 + "QueryInterface requires a non-NULL destination!");
1.381 + nsresult rv = NS_ERROR_FAILURE;
1.382 + NS_INTERFACE_TABLE(ExpirationTrackerObserver, nsIObserver)
1.383 + return rv;
1.384 +}
1.385 +
1.386 +#endif /*NSEXPIRATIONTRACKER_H_*/
