1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #ifndef NSEXPIRATIONTRACKER_H_
8 #define NSEXPIRATIONTRACKER_H_
11 #include "MainThreadUtils.h"
12 #include "nsAlgorithm.h"
17 #include "nsIEventTarget.h"
18 #include "nsIObserver.h"
19 #include "nsIObserverService.h"
20 #include "nsISupports.h"
21 #include "nsIThread.h"
22 #include "nsThreadUtils.h"
24 #include "mozilla/Assertions.h"
25 #include "mozilla/Likely.h"
26 #include "mozilla/MemoryReporting.h"
27 #include "mozilla/RefCountType.h"
28 #include "mozilla/RefPtr.h"
29 #include "mozilla/Services.h"
32 * Data used to track the expiration state of an object. We promise that this
33 * is 32 bits so that objects that includes this as a field can pad and align
36 struct nsExpirationState
{
38 NOT_TRACKED
= (1U << 4) - 1,
39 MAX_INDEX_IN_GENERATION
= (1U << 28) - 1
42 nsExpirationState() : mGeneration(NOT_TRACKED
), mIndexInGeneration(0) {}
43 bool IsTracked() { return mGeneration
!= NOT_TRACKED
; }
46 * The generation that this object belongs to, or NOT_TRACKED.
48 uint32_t mGeneration
: 4;
49 uint32_t mIndexInGeneration
: 28;
53 * ExpirationTracker classes:
54 * - ExpirationTrackerImpl (Thread-safe class)
55 * - nsExpirationTracker (Main-thread only class)
57 * These classes can track the lifetimes and usage of a large number of
58 * objects, and send a notification some window of time after a live object was
59 * last used. This is very useful when you manage a large number of objects
60 * and want to flush some after they haven't been used for a while.
61 * nsExpirationTracker is designed to be very space and time efficient.
63 * The type parameter T is the object type that we will track pointers to. T
64 * must include an accessible method GetExpirationState() that returns a
65 * pointer to an nsExpirationState associated with the object (preferably,
66 * stored in a field of the object).
68 * The parameter K is the number of generations that will be used. Increasing
69 * the number of generations narrows the window within which we promise
70 * to fire notifications, at a slight increase in space cost for the tracker.
71 * We require 2 <= K <= nsExpirationState::NOT_TRACKED (currently 15).
73 * To use this class, you need to inherit from it and override the
74 * NotifyExpired() method.
76 * The approach is to track objects in K generations. When an object is accessed
77 * it moves from its current generation to the newest generation. Generations
78 * are stored in a cyclic array; when a timer interrupt fires, we advance
79 * the current generation pointer to effectively age all objects very
80 * efficiently. By storing information in each object about its generation and
81 * index within its generation array, we make removal of objects from a
82 * generation very cheap.
85 * -- Add a method to change the timer period?
89 * Base class for ExiprationTracker implementations.
91 * nsExpirationTracker class below is a specialized class to be inherited by the
92 * instances to be accessed only on main-thread.
94 * For creating a thread-safe tracker, you can define a subclass inheriting this
95 * base class and specialize the Mutex and AutoLock to be used.
97 * For an example of using ExpirationTrackerImpl with a DataMutex
98 * @see mozilla::gfx::GradientCache.
101 template <typename T
, uint32_t K
, typename Mutex
, typename AutoLock
>
102 class ExpirationTrackerImpl
{
105 * Initialize the tracker.
106 * @param aTimerPeriod the timer period in milliseconds. The guarantees
107 * provided by the tracker are defined in terms of this period. If the
108 * period is zero, then we don't use a timer and rely on someone calling
109 * AgeOneGenerationLocked explicitly.
110 * @param aName the name of the subclass for telemetry.
111 * @param aEventTarget the optional event target on main thread to label the
112 * runnable of the asynchronous invocation to NotifyExpired().
115 ExpirationTrackerImpl(uint32_t aTimerPeriod
, const char* aName
,
116 nsIEventTarget
* aEventTarget
= nullptr)
117 : mTimerPeriod(aTimerPeriod
),
118 mNewestGeneration(0),
119 mInAgeOneGeneration(false),
121 mEventTarget(aEventTarget
) {
122 static_assert(K
>= 2 && K
<= nsExpirationState::NOT_TRACKED
,
123 "Unsupported number of generations (must be 2 <= K <= 15)");
124 // If we are not initialized on the main thread, the owner is responsible
125 // for dealing with memory pressure events.
126 if (NS_IsMainThread()) {
127 mObserver
= new ExpirationTrackerObserver();
128 mObserver
->Init(this);
132 virtual ~ExpirationTrackerImpl() {
137 MOZ_ASSERT(NS_IsMainThread());
138 mObserver
->Destroy();
143 * Add an object to be tracked. It must not already be tracked. It will
144 * be added to the newest generation, i.e., as if it was just used.
145 * @return an error on out-of-memory
147 nsresult
AddObjectLocked(T
* aObj
, const AutoLock
& aAutoLock
) {
148 if (NS_WARN_IF(!aObj
)) {
149 MOZ_DIAGNOSTIC_ASSERT(false, "Invalid object to add");
150 return NS_ERROR_UNEXPECTED
;
152 nsExpirationState
* state
= aObj
->GetExpirationState();
153 if (NS_WARN_IF(state
->IsTracked())) {
154 MOZ_DIAGNOSTIC_ASSERT(false,
155 "Tried to add an object that's already tracked");
156 return NS_ERROR_UNEXPECTED
;
158 nsTArray
<T
*>& generation
= mGenerations
[mNewestGeneration
];
159 uint32_t index
= generation
.Length();
160 if (index
> nsExpirationState::MAX_INDEX_IN_GENERATION
) {
161 NS_WARNING("More than 256M elements tracked, this is probably a problem");
162 return NS_ERROR_OUT_OF_MEMORY
;
165 // We might need to start the timer
166 nsresult rv
= CheckStartTimerLocked(aAutoLock
);
171 // XXX(Bug 1631371) Check if this should use a fallible operation as it
172 // pretended earlier.
173 generation
.AppendElement(aObj
);
174 state
->mGeneration
= mNewestGeneration
;
175 state
->mIndexInGeneration
= index
;
180 * Remove an object from the tracker. It must currently be tracked.
182 void RemoveObjectLocked(T
* aObj
, const AutoLock
& aAutoLock
) {
183 if (NS_WARN_IF(!aObj
)) {
184 MOZ_DIAGNOSTIC_ASSERT(false, "Invalid object to remove");
187 nsExpirationState
* state
= aObj
->GetExpirationState();
188 if (NS_WARN_IF(!state
->IsTracked())) {
189 MOZ_DIAGNOSTIC_ASSERT(false,
190 "Tried to remove an object that's not tracked");
193 nsTArray
<T
*>& generation
= mGenerations
[state
->mGeneration
];
194 uint32_t index
= state
->mIndexInGeneration
;
195 MOZ_ASSERT(generation
.Length() > index
&& generation
[index
] == aObj
,
196 "Object is lying about its index");
197 // Move the last object to fill the hole created by removing aObj
198 T
* lastObj
= generation
.PopLastElement();
199 // XXX It looks weird that index might point to the element that was just
200 // removed. Is that really correct?
201 if (index
< generation
.Length()) {
202 generation
[index
] = lastObj
;
204 lastObj
->GetExpirationState()->mIndexInGeneration
= index
;
205 state
->mGeneration
= nsExpirationState::NOT_TRACKED
;
206 // We do not check whether we need to stop the timer here. The timer
207 // will check that itself next time it fires. Checking here would not
208 // be efficient since we'd need to track all generations. Also we could
209 // thrash by incessantly creating and destroying timers if someone
210 // kept adding and removing an object from the tracker.
214 * Notify that an object has been used.
215 * @return an error if we lost the object from the tracker...
217 nsresult
MarkUsedLocked(T
* aObj
, const AutoLock
& aAutoLock
) {
218 nsExpirationState
* state
= aObj
->GetExpirationState();
219 if (mNewestGeneration
== state
->mGeneration
) {
222 RemoveObjectLocked(aObj
, aAutoLock
);
223 return AddObjectLocked(aObj
, aAutoLock
);
227 * The timer calls this, but it can also be manually called if you want
228 * to age objects "artifically". This can result in calls to
229 * NotifyExpiredLocked.
231 void AgeOneGenerationLocked(const AutoLock
& aAutoLock
) {
232 if (mInAgeOneGeneration
) {
233 NS_WARNING("Can't reenter AgeOneGeneration from NotifyExpired");
237 mInAgeOneGeneration
= true;
238 uint32_t reapGeneration
=
239 mNewestGeneration
> 0 ? mNewestGeneration
- 1 : K
- 1;
240 nsTArray
<T
*>& generation
= mGenerations
[reapGeneration
];
241 // The following is rather tricky. We have to cope with objects being
242 // removed from this generation either because of a call to RemoveObject
243 // (or indirectly via MarkUsedLocked) inside NotifyExpiredLocked.
244 // Fortunately no objects can be added to this generation because it's not
245 // the newest generation. We depend on the fact that RemoveObject can only
246 // cause the indexes of objects in this generation to *decrease*, not
247 // increase. So if we start from the end and work our way backwards we are
248 // guaranteed to see each object at least once.
249 size_t index
= generation
.Length();
251 // Objects could have been removed so index could be outside
253 index
= XPCOM_MIN(index
, generation
.Length());
258 NotifyExpiredLocked(generation
[index
], aAutoLock
);
260 // Any leftover objects from reapGeneration just end up in the new
261 // newest-generation. This is bad form, though, so warn if there are any.
262 if (!generation
.IsEmpty()) {
263 NS_WARNING("Expired objects were not removed or marked used");
265 // Free excess memory used by the generation array, since we probably
266 // just removed most or all of its elements.
267 generation
.Compact();
268 mNewestGeneration
= reapGeneration
;
269 mInAgeOneGeneration
= false;
273 * This just calls AgeOneGenerationLocked K times. Under normal circumstances
274 * this will result in all objects getting NotifyExpiredLocked called on them,
275 * but if NotifyExpiredLocked itself marks some objects as used, then those
276 * objects might not expire. This would be a good thing to call if we get into
277 * a critically-low memory situation.
279 void AgeAllGenerationsLocked(const AutoLock
& aAutoLock
) {
281 for (i
= 0; i
< K
; ++i
) {
282 AgeOneGenerationLocked(aAutoLock
);
288 ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>* mTracker
;
289 uint32_t mGeneration
;
293 Iterator(ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>* aTracker
,
295 : mTracker(aTracker
), mGeneration(0), mIndex(0) {}
298 while (mGeneration
< K
) {
299 nsTArray
<T
*>* generation
= &mTracker
->mGenerations
[mGeneration
];
300 if (mIndex
< generation
->Length()) {
302 return (*generation
)[mIndex
- 1];
311 friend class Iterator
;
313 bool IsEmptyLocked(const AutoLock
& aAutoLock
) const {
314 for (uint32_t i
= 0; i
< K
; ++i
) {
315 if (!mGenerations
[i
].IsEmpty()) {
322 size_t Length(const AutoLock
& aAutoLock
) const {
324 for (uint32_t i
= 0; i
< K
; ++i
) {
325 len
+= mGenerations
[i
].Length();
330 // @return The amount of memory used by this ExpirationTrackerImpl, excluding
331 // sizeof(*this). If you want to measure anything hanging off the mGenerations
332 // array, you must iterate over the elements and measure them individually;
333 // hence the "Shallow" prefix.
334 size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const {
336 for (uint32_t i
= 0; i
< K
; ++i
) {
337 bytes
+= mGenerations
[i
].ShallowSizeOfExcludingThis(aMallocSizeOf
);
344 * This must be overridden to catch notifications. It is called whenever
345 * we detect that an object has not been used for at least (K-1)*mTimerPeriod
346 * milliseconds. If timer events are not delayed, it will be called within
347 * roughly K*mTimerPeriod milliseconds after the last use.
348 * (Unless AgeOneGenerationLocked or AgeAllGenerationsLocked have been called
349 * to accelerate the aging process.)
351 * NOTE: These bounds ignore delays in timer firings due to actual work being
352 * performed by the browser. We use a slack timer so there is always at least
353 * mTimerPeriod milliseconds between firings, which gives us
354 * (K-1)*mTimerPeriod as a pretty solid lower bound. The upper bound is rather
355 * loose, however. If the maximum amount by which any given timer firing is
356 * delayed is D, then the upper bound before NotifyExpiredLocked is called is
357 * K*(mTimerPeriod + D).
359 * The NotifyExpiredLocked call is expected to remove the object from the
360 * tracker, but it need not. The object (or other objects) could be
361 * "resurrected" by calling MarkUsedLocked() on them, or they might just not
362 * be removed. Any objects left over that have not been resurrected or removed
363 * are placed in the new newest-generation, but this is considered "bad form"
364 * and should be avoided (we'll issue a warning). (This recycling counts
365 * as "a use" for the purposes of the expiry guarantee above...)
367 * For robustness and simplicity, we allow objects to be notified more than
368 * once here in the same timer tick.
370 virtual void NotifyExpiredLocked(T
*, const AutoLock
&) = 0;
373 * This may be overridden to perform any post-aging work that needs to be
374 * done while still holding the lock. It will be called once after each timer
375 * event, and each low memory event has been handled.
377 virtual void NotifyHandlerEndLocked(const AutoLock
&){};
380 * This may be overridden to perform any post-aging work that needs to be
381 * done outside the lock. It will be called once after each
382 * NotifyEndTransactionLocked call.
384 virtual void NotifyHandlerEnd(){};
386 virtual Mutex
& GetMutex() = 0;
389 class ExpirationTrackerObserver
;
390 RefPtr
<ExpirationTrackerObserver
> mObserver
;
391 nsTArray
<T
*> mGenerations
[K
];
392 nsCOMPtr
<nsITimer
> mTimer
;
393 uint32_t mTimerPeriod
;
394 uint32_t mNewestGeneration
;
395 bool mInAgeOneGeneration
;
396 const char* const mName
; // Used for timer firing profiling.
397 const nsCOMPtr
<nsIEventTarget
> mEventTarget
;
400 * Whenever "memory-pressure" is observed, it calls AgeAllGenerationsLocked()
401 * to minimize memory usage.
403 class ExpirationTrackerObserver final
: public nsIObserver
{
405 void Init(ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>* aObj
) {
407 nsCOMPtr
<nsIObserverService
> obs
=
408 mozilla::services::GetObserverService();
410 obs
->AddObserver(this, "memory-pressure", false);
415 nsCOMPtr
<nsIObserverService
> obs
=
416 mozilla::services::GetObserverService();
418 obs
->RemoveObserver(this, "memory-pressure");
424 ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>* mOwner
;
427 void HandleLowMemory() {
429 AutoLock
lock(GetMutex());
430 AgeAllGenerationsLocked(lock
);
431 NotifyHandlerEndLocked(lock
);
436 void HandleTimeout() {
438 AutoLock
lock(GetMutex());
439 AgeOneGenerationLocked(lock
);
440 // Cancel the timer if we have no objects to track
441 if (IsEmptyLocked(lock
)) {
445 NotifyHandlerEndLocked(lock
);
450 static void TimerCallback(nsITimer
* aTimer
, void* aThis
) {
451 ExpirationTrackerImpl
* tracker
= static_cast<ExpirationTrackerImpl
*>(aThis
);
452 tracker
->HandleTimeout();
455 nsresult
CheckStartTimerLocked(const AutoLock
& aAutoLock
) {
456 if (mTimer
|| !mTimerPeriod
) {
460 return NS_NewTimerWithFuncCallback(
461 getter_AddRefs(mTimer
), TimerCallback
, this, mTimerPeriod
,
462 nsITimer::TYPE_REPEATING_SLACK_LOW_PRIORITY
, mName
, mEventTarget
);
468 class PlaceholderLock
{
474 class PlaceholderAutoLock
{
476 explicit PlaceholderAutoLock(PlaceholderLock
&) {}
477 ~PlaceholderAutoLock() = default;
480 template <typename T
, uint32_t K
>
481 using SingleThreadedExpirationTracker
=
482 ExpirationTrackerImpl
<T
, K
, PlaceholderLock
, PlaceholderAutoLock
>;
484 } // namespace detail
486 template <typename T
, uint32_t K
>
487 class nsExpirationTracker
488 : protected ::detail::SingleThreadedExpirationTracker
<T
, K
> {
489 typedef ::detail::PlaceholderLock Lock
;
490 typedef ::detail::PlaceholderAutoLock AutoLock
;
494 AutoLock
FakeLock() {
495 NS_ASSERT_OWNINGTHREAD(nsExpirationTracker
);
496 return AutoLock(mLock
);
499 Lock
& GetMutex() override
{
500 NS_ASSERT_OWNINGTHREAD(nsExpirationTracker
);
504 void NotifyExpiredLocked(T
* aObject
, const AutoLock
&) override
{
505 NotifyExpired(aObject
);
509 * Since there are no users of these callbacks in the single threaded case,
510 * we mark them as final with the hope that the compiler can optimize the
511 * method calls out entirely.
513 void NotifyHandlerEndLocked(const AutoLock
&) final
{}
514 void NotifyHandlerEnd() final
{}
519 virtual void NotifyExpired(T
* aObj
) = 0;
522 nsExpirationTracker(uint32_t aTimerPeriod
, const char* aName
,
523 nsIEventTarget
* aEventTarget
= nullptr)
524 : ::detail::SingleThreadedExpirationTracker
<T
, K
>(aTimerPeriod
, aName
,
527 virtual ~nsExpirationTracker() {
528 NS_ASSERT_OWNINGTHREAD(nsExpirationTracker
);
531 nsresult
AddObject(T
* aObj
) {
532 return this->AddObjectLocked(aObj
, FakeLock());
535 void RemoveObject(T
* aObj
) { this->RemoveObjectLocked(aObj
, FakeLock()); }
537 nsresult
MarkUsed(T
* aObj
) { return this->MarkUsedLocked(aObj
, FakeLock()); }
539 void AgeOneGeneration() { this->AgeOneGenerationLocked(FakeLock()); }
541 void AgeAllGenerations() { this->AgeAllGenerationsLocked(FakeLock()); }
546 typename ExpirationTrackerImpl
<T
, K
, Lock
, AutoLock
>::Iterator mIterator
;
549 explicit Iterator(nsExpirationTracker
<T
, K
>* aTracker
)
550 : mAutoLock(aTracker
->GetMutex()), mIterator(aTracker
, mAutoLock
) {}
552 T
* Next() { return mIterator
.Next(); }
555 friend class Iterator
;
557 bool IsEmpty() { return this->IsEmptyLocked(FakeLock()); }
560 template <typename T
, uint32_t K
, typename Mutex
, typename AutoLock
>
561 NS_IMETHODIMP ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>::
562 ExpirationTrackerObserver::Observe(nsISupports
* aSubject
,
564 const char16_t
* aData
) {
565 if (!strcmp(aTopic
, "memory-pressure") && mOwner
) {
566 mOwner
->HandleLowMemory();
571 template <class T
, uint32_t K
, typename Mutex
, typename AutoLock
>
572 NS_IMETHODIMP_(MozExternalRefCountType
)
573 ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>::ExpirationTrackerObserver::AddRef(
575 MOZ_ASSERT(int32_t(mRefCnt
) >= 0, "illegal refcnt");
576 NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver
);
578 NS_LOG_ADDREF(this, mRefCnt
, "ExpirationTrackerObserver", sizeof(*this));
582 template <class T
, uint32_t K
, typename Mutex
, typename AutoLock
>
583 NS_IMETHODIMP_(MozExternalRefCountType
)
584 ExpirationTrackerImpl
<T
, K
, Mutex
,
585 AutoLock
>::ExpirationTrackerObserver::Release(void) {
586 MOZ_ASSERT(int32_t(mRefCnt
) > 0, "dup release");
587 NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver
);
589 NS_LOG_RELEASE(this, mRefCnt
, "ExpirationTrackerObserver");
591 NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver
);
592 mRefCnt
= 1; /* stabilize */
599 template <class T
, uint32_t K
, typename Mutex
, typename AutoLock
>
600 NS_IMETHODIMP ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>::
601 ExpirationTrackerObserver::QueryInterface(REFNSIID aIID
,
602 void** aInstancePtr
) {
603 NS_ASSERTION(aInstancePtr
, "QueryInterface requires a non-NULL destination!");
604 nsresult rv
= NS_ERROR_FAILURE
;
605 NS_INTERFACE_TABLE(ExpirationTrackerObserver
, nsIObserver
)
609 #endif /*NSEXPIRATIONTRACKER_H_*/