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 MOZ_ASSERT(NS_IsMainThread());
126 bool current
= false;
127 // NOTE: The following check+crash could be condensed into a
128 // MOZ_RELEASE_ASSERT, but that triggers a segfault during compilation in
129 // clang 3.8. Once we don't have to care about clang 3.8 anymore, though,
130 // we can convert to MOZ_RELEASE_ASSERT here.
131 if (MOZ_UNLIKELY(NS_FAILED(mEventTarget
->IsOnCurrentThread(¤t
)) ||
133 MOZ_CRASH("Provided event target must be on the main thread");
136 mObserver
= new ExpirationTrackerObserver();
137 mObserver
->Init(this);
140 virtual ~ExpirationTrackerImpl() {
141 MOZ_ASSERT(NS_IsMainThread());
145 mObserver
->Destroy();
149 * Add an object to be tracked. It must not already be tracked. It will
150 * be added to the newest generation, i.e., as if it was just used.
151 * @return an error on out-of-memory
153 nsresult
AddObjectLocked(T
* aObj
, const AutoLock
& aAutoLock
) {
154 if (NS_WARN_IF(!aObj
)) {
155 MOZ_DIAGNOSTIC_ASSERT(false, "Invalid object to add");
156 return NS_ERROR_UNEXPECTED
;
158 nsExpirationState
* state
= aObj
->GetExpirationState();
159 if (NS_WARN_IF(state
->IsTracked())) {
160 MOZ_DIAGNOSTIC_ASSERT(false,
161 "Tried to add an object that's already tracked");
162 return NS_ERROR_UNEXPECTED
;
164 nsTArray
<T
*>& generation
= mGenerations
[mNewestGeneration
];
165 uint32_t index
= generation
.Length();
166 if (index
> nsExpirationState::MAX_INDEX_IN_GENERATION
) {
167 NS_WARNING("More than 256M elements tracked, this is probably a problem");
168 return NS_ERROR_OUT_OF_MEMORY
;
171 // We might need to start the timer
172 nsresult rv
= CheckStartTimerLocked(aAutoLock
);
177 // XXX(Bug 1631371) Check if this should use a fallible operation as it
178 // pretended earlier.
179 generation
.AppendElement(aObj
);
180 state
->mGeneration
= mNewestGeneration
;
181 state
->mIndexInGeneration
= index
;
186 * Remove an object from the tracker. It must currently be tracked.
188 void RemoveObjectLocked(T
* aObj
, const AutoLock
& aAutoLock
) {
189 if (NS_WARN_IF(!aObj
)) {
190 MOZ_DIAGNOSTIC_ASSERT(false, "Invalid object to remove");
193 nsExpirationState
* state
= aObj
->GetExpirationState();
194 if (NS_WARN_IF(!state
->IsTracked())) {
195 MOZ_DIAGNOSTIC_ASSERT(false,
196 "Tried to remove an object that's not tracked");
199 nsTArray
<T
*>& generation
= mGenerations
[state
->mGeneration
];
200 uint32_t index
= state
->mIndexInGeneration
;
201 MOZ_ASSERT(generation
.Length() > index
&& generation
[index
] == aObj
,
202 "Object is lying about its index");
203 // Move the last object to fill the hole created by removing aObj
204 T
* lastObj
= generation
.PopLastElement();
205 // XXX It looks weird that index might point to the element that was just
206 // removed. Is that really correct?
207 if (index
< generation
.Length()) {
208 generation
[index
] = lastObj
;
210 lastObj
->GetExpirationState()->mIndexInGeneration
= index
;
211 state
->mGeneration
= nsExpirationState::NOT_TRACKED
;
212 // We do not check whether we need to stop the timer here. The timer
213 // will check that itself next time it fires. Checking here would not
214 // be efficient since we'd need to track all generations. Also we could
215 // thrash by incessantly creating and destroying timers if someone
216 // kept adding and removing an object from the tracker.
220 * Notify that an object has been used.
221 * @return an error if we lost the object from the tracker...
223 nsresult
MarkUsedLocked(T
* aObj
, const AutoLock
& aAutoLock
) {
224 nsExpirationState
* state
= aObj
->GetExpirationState();
225 if (mNewestGeneration
== state
->mGeneration
) {
228 RemoveObjectLocked(aObj
, aAutoLock
);
229 return AddObjectLocked(aObj
, aAutoLock
);
233 * The timer calls this, but it can also be manually called if you want
234 * to age objects "artifically". This can result in calls to
235 * NotifyExpiredLocked.
237 void AgeOneGenerationLocked(const AutoLock
& aAutoLock
) {
238 if (mInAgeOneGeneration
) {
239 NS_WARNING("Can't reenter AgeOneGeneration from NotifyExpired");
243 mInAgeOneGeneration
= true;
244 uint32_t reapGeneration
=
245 mNewestGeneration
> 0 ? mNewestGeneration
- 1 : K
- 1;
246 nsTArray
<T
*>& generation
= mGenerations
[reapGeneration
];
247 // The following is rather tricky. We have to cope with objects being
248 // removed from this generation either because of a call to RemoveObject
249 // (or indirectly via MarkUsedLocked) inside NotifyExpiredLocked.
250 // Fortunately no objects can be added to this generation because it's not
251 // the newest generation. We depend on the fact that RemoveObject can only
252 // cause the indexes of objects in this generation to *decrease*, not
253 // increase. So if we start from the end and work our way backwards we are
254 // guaranteed to see each object at least once.
255 size_t index
= generation
.Length();
257 // Objects could have been removed so index could be outside
259 index
= XPCOM_MIN(index
, generation
.Length());
264 NotifyExpiredLocked(generation
[index
], aAutoLock
);
266 // Any leftover objects from reapGeneration just end up in the new
267 // newest-generation. This is bad form, though, so warn if there are any.
268 if (!generation
.IsEmpty()) {
269 NS_WARNING("Expired objects were not removed or marked used");
271 // Free excess memory used by the generation array, since we probably
272 // just removed most or all of its elements.
273 generation
.Compact();
274 mNewestGeneration
= reapGeneration
;
275 mInAgeOneGeneration
= false;
279 * This just calls AgeOneGenerationLocked K times. Under normal circumstances
280 * this will result in all objects getting NotifyExpiredLocked called on them,
281 * but if NotifyExpiredLocked itself marks some objects as used, then those
282 * objects might not expire. This would be a good thing to call if we get into
283 * a critically-low memory situation.
285 void AgeAllGenerationsLocked(const AutoLock
& aAutoLock
) {
287 for (i
= 0; i
< K
; ++i
) {
288 AgeOneGenerationLocked(aAutoLock
);
294 ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>* mTracker
;
295 uint32_t mGeneration
;
299 Iterator(ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>* aTracker
,
301 : mTracker(aTracker
), mGeneration(0), mIndex(0) {}
304 while (mGeneration
< K
) {
305 nsTArray
<T
*>* generation
= &mTracker
->mGenerations
[mGeneration
];
306 if (mIndex
< generation
->Length()) {
308 return (*generation
)[mIndex
- 1];
317 friend class Iterator
;
319 bool IsEmptyLocked(const AutoLock
& aAutoLock
) const {
320 for (uint32_t i
= 0; i
< K
; ++i
) {
321 if (!mGenerations
[i
].IsEmpty()) {
328 size_t Length(const AutoLock
& aAutoLock
) const {
330 for (uint32_t i
= 0; i
< K
; ++i
) {
331 len
+= mGenerations
[i
].Length();
336 // @return The amount of memory used by this ExpirationTrackerImpl, excluding
337 // sizeof(*this). If you want to measure anything hanging off the mGenerations
338 // array, you must iterate over the elements and measure them individually;
339 // hence the "Shallow" prefix.
340 size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const {
342 for (uint32_t i
= 0; i
< K
; ++i
) {
343 bytes
+= mGenerations
[i
].ShallowSizeOfExcludingThis(aMallocSizeOf
);
350 * This must be overridden to catch notifications. It is called whenever
351 * we detect that an object has not been used for at least (K-1)*mTimerPeriod
352 * milliseconds. If timer events are not delayed, it will be called within
353 * roughly K*mTimerPeriod milliseconds after the last use.
354 * (Unless AgeOneGenerationLocked or AgeAllGenerationsLocked have been called
355 * to accelerate the aging process.)
357 * NOTE: These bounds ignore delays in timer firings due to actual work being
358 * performed by the browser. We use a slack timer so there is always at least
359 * mTimerPeriod milliseconds between firings, which gives us
360 * (K-1)*mTimerPeriod as a pretty solid lower bound. The upper bound is rather
361 * loose, however. If the maximum amount by which any given timer firing is
362 * delayed is D, then the upper bound before NotifyExpiredLocked is called is
363 * K*(mTimerPeriod + D).
365 * The NotifyExpiredLocked call is expected to remove the object from the
366 * tracker, but it need not. The object (or other objects) could be
367 * "resurrected" by calling MarkUsedLocked() on them, or they might just not
368 * be removed. Any objects left over that have not been resurrected or removed
369 * are placed in the new newest-generation, but this is considered "bad form"
370 * and should be avoided (we'll issue a warning). (This recycling counts
371 * as "a use" for the purposes of the expiry guarantee above...)
373 * For robustness and simplicity, we allow objects to be notified more than
374 * once here in the same timer tick.
376 virtual void NotifyExpiredLocked(T
*, const AutoLock
&) = 0;
379 * This may be overridden to perform any post-aging work that needs to be
380 * done while still holding the lock. It will be called once after each timer
381 * event, and each low memory event has been handled.
383 virtual void NotifyHandlerEndLocked(const AutoLock
&){};
386 * This may be overridden to perform any post-aging work that needs to be
387 * done outside the lock. It will be called once after each
388 * NotifyEndTransactionLocked call.
390 virtual void NotifyHandlerEnd(){};
392 virtual Mutex
& GetMutex() = 0;
395 class ExpirationTrackerObserver
;
396 RefPtr
<ExpirationTrackerObserver
> mObserver
;
397 nsTArray
<T
*> mGenerations
[K
];
398 nsCOMPtr
<nsITimer
> mTimer
;
399 uint32_t mTimerPeriod
;
400 uint32_t mNewestGeneration
;
401 bool mInAgeOneGeneration
;
402 const char* const mName
; // Used for timer firing profiling.
403 const nsCOMPtr
<nsIEventTarget
> mEventTarget
;
406 * Whenever "memory-pressure" is observed, it calls AgeAllGenerationsLocked()
407 * to minimize memory usage.
409 class ExpirationTrackerObserver final
: public nsIObserver
{
411 void Init(ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>* aObj
) {
413 nsCOMPtr
<nsIObserverService
> obs
=
414 mozilla::services::GetObserverService();
416 obs
->AddObserver(this, "memory-pressure", false);
421 nsCOMPtr
<nsIObserverService
> obs
=
422 mozilla::services::GetObserverService();
424 obs
->RemoveObserver(this, "memory-pressure");
430 ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>* mOwner
;
433 void HandleLowMemory() {
435 AutoLock
lock(GetMutex());
436 AgeAllGenerationsLocked(lock
);
437 NotifyHandlerEndLocked(lock
);
442 void HandleTimeout() {
444 AutoLock
lock(GetMutex());
445 AgeOneGenerationLocked(lock
);
446 // Cancel the timer if we have no objects to track
447 if (IsEmptyLocked(lock
)) {
451 NotifyHandlerEndLocked(lock
);
456 static void TimerCallback(nsITimer
* aTimer
, void* aThis
) {
457 ExpirationTrackerImpl
* tracker
= static_cast<ExpirationTrackerImpl
*>(aThis
);
458 tracker
->HandleTimeout();
461 nsresult
CheckStartTimerLocked(const AutoLock
& aAutoLock
) {
462 if (mTimer
|| !mTimerPeriod
) {
465 nsCOMPtr
<nsIEventTarget
> target
= mEventTarget
;
466 if (!target
&& !NS_IsMainThread()) {
467 // TimerCallback should always be run on the main thread to prevent races
468 // to the destruction of the tracker.
469 target
= do_GetMainThread();
470 NS_ENSURE_STATE(target
);
473 return NS_NewTimerWithFuncCallback(
474 getter_AddRefs(mTimer
), TimerCallback
, this, mTimerPeriod
,
475 nsITimer::TYPE_REPEATING_SLACK_LOW_PRIORITY
, mName
, target
);
481 class PlaceholderLock
{
487 class PlaceholderAutoLock
{
489 explicit PlaceholderAutoLock(PlaceholderLock
&) {}
490 ~PlaceholderAutoLock() = default;
493 template <typename T
, uint32_t K
>
494 using SingleThreadedExpirationTracker
=
495 ExpirationTrackerImpl
<T
, K
, PlaceholderLock
, PlaceholderAutoLock
>;
497 } // namespace detail
499 template <typename T
, uint32_t K
>
500 class nsExpirationTracker
501 : protected ::detail::SingleThreadedExpirationTracker
<T
, K
> {
502 typedef ::detail::PlaceholderLock Lock
;
503 typedef ::detail::PlaceholderAutoLock AutoLock
;
507 AutoLock
FakeLock() {
508 MOZ_DIAGNOSTIC_ASSERT(NS_IsMainThread());
509 return AutoLock(mLock
);
512 Lock
& GetMutex() override
{
513 MOZ_DIAGNOSTIC_ASSERT(NS_IsMainThread());
517 void NotifyExpiredLocked(T
* aObject
, const AutoLock
&) override
{
518 NotifyExpired(aObject
);
522 * Since there are no users of these callbacks in the single threaded case,
523 * we mark them as final with the hope that the compiler can optimize the
524 * method calls out entirely.
526 void NotifyHandlerEndLocked(const AutoLock
&) final
{}
527 void NotifyHandlerEnd() final
{}
530 virtual void NotifyExpired(T
* aObj
) = 0;
533 nsExpirationTracker(uint32_t aTimerPeriod
, const char* aName
,
534 nsIEventTarget
* aEventTarget
= nullptr)
535 : ::detail::SingleThreadedExpirationTracker
<T
, K
>(aTimerPeriod
, aName
,
538 virtual ~nsExpirationTracker() = default;
540 nsresult
AddObject(T
* aObj
) {
541 return this->AddObjectLocked(aObj
, FakeLock());
544 void RemoveObject(T
* aObj
) { this->RemoveObjectLocked(aObj
, FakeLock()); }
546 nsresult
MarkUsed(T
* aObj
) { return this->MarkUsedLocked(aObj
, FakeLock()); }
548 void AgeOneGeneration() { this->AgeOneGenerationLocked(FakeLock()); }
550 void AgeAllGenerations() { this->AgeAllGenerationsLocked(FakeLock()); }
555 typename ExpirationTrackerImpl
<T
, K
, Lock
, AutoLock
>::Iterator mIterator
;
558 explicit Iterator(nsExpirationTracker
<T
, K
>* aTracker
)
559 : mAutoLock(aTracker
->GetMutex()), mIterator(aTracker
, mAutoLock
) {}
561 T
* Next() { return mIterator
.Next(); }
564 friend class Iterator
;
566 bool IsEmpty() { return this->IsEmptyLocked(FakeLock()); }
569 template <typename T
, uint32_t K
, typename Mutex
, typename AutoLock
>
570 NS_IMETHODIMP ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>::
571 ExpirationTrackerObserver::Observe(nsISupports
* aSubject
,
573 const char16_t
* aData
) {
574 if (!strcmp(aTopic
, "memory-pressure") && mOwner
) {
575 mOwner
->HandleLowMemory();
580 template <class T
, uint32_t K
, typename Mutex
, typename AutoLock
>
581 NS_IMETHODIMP_(MozExternalRefCountType
)
582 ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>::ExpirationTrackerObserver::AddRef(
584 MOZ_ASSERT(int32_t(mRefCnt
) >= 0, "illegal refcnt");
585 NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver
);
587 NS_LOG_ADDREF(this, mRefCnt
, "ExpirationTrackerObserver", sizeof(*this));
591 template <class T
, uint32_t K
, typename Mutex
, typename AutoLock
>
592 NS_IMETHODIMP_(MozExternalRefCountType
)
593 ExpirationTrackerImpl
<T
, K
, Mutex
,
594 AutoLock
>::ExpirationTrackerObserver::Release(void) {
595 MOZ_ASSERT(int32_t(mRefCnt
) > 0, "dup release");
596 NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver
);
598 NS_LOG_RELEASE(this, mRefCnt
, "ExpirationTrackerObserver");
600 NS_ASSERT_OWNINGTHREAD(ExpirationTrackerObserver
);
601 mRefCnt
= 1; /* stabilize */
608 template <class T
, uint32_t K
, typename Mutex
, typename AutoLock
>
609 NS_IMETHODIMP ExpirationTrackerImpl
<T
, K
, Mutex
, AutoLock
>::
610 ExpirationTrackerObserver::QueryInterface(REFNSIID aIID
,
611 void** aInstancePtr
) {
612 NS_ASSERTION(aInstancePtr
, "QueryInterface requires a non-NULL destination!");
613 nsresult rv
= NS_ERROR_FAILURE
;
614 NS_INTERFACE_TABLE(ExpirationTrackerObserver
, nsIObserver
)
618 #endif /*NSEXPIRATIONTRACKER_H_*/