Source code

Revision control

Copy as Markdown

Other Tools

/* -*- 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/. */
#include "gc/Scheduling.h"
#include "mozilla/CheckedInt.h"
#include "mozilla/ScopeExit.h"
#include "mozilla/TimeStamp.h"
#include <algorithm>
#include <cmath>
#include "gc/Memory.h"
#include "gc/Nursery.h"
#include "gc/RelocationOverlay.h"
#include "gc/ZoneAllocator.h"
#include "util/DifferentialTesting.h"
#include "vm/MutexIDs.h"
using namespace js;
using namespace js::gc;
using mozilla::CheckedInt;
using mozilla::Maybe;
using mozilla::Nothing;
using mozilla::Some;
using mozilla::TimeDuration;
/*
* We may start to collect a zone before its trigger threshold is reached if
* GCRuntime::maybeGC() is called for that zone or we start collecting other
* zones. These eager threshold factors are not configurable.
*/
static constexpr double HighFrequencyEagerAllocTriggerFactor = 0.85;
static constexpr double LowFrequencyEagerAllocTriggerFactor = 0.9;
/*
* Don't allow heap growth factors to be set so low that eager collections could
* reduce the trigger threshold.
*/
static constexpr double MinHeapGrowthFactor =
1.0f / std::min(HighFrequencyEagerAllocTriggerFactor,
LowFrequencyEagerAllocTriggerFactor);
// Limit various parameters to reasonable levels to catch errors.
static constexpr double MaxHeapGrowthFactor = 100;
static constexpr size_t MaxNurseryBytesParam = 128 * 1024 * 1024;
namespace {
// Helper classes to marshal GC parameter values to/from uint32_t.
template <typename T>
struct ConvertGeneric {
static uint32_t toUint32(T value) {
static_assert(std::is_arithmetic_v<T>);
if constexpr (std::is_signed_v<T>) {
MOZ_ASSERT(value >= 0);
}
if constexpr (!std::is_same_v<T, bool> &&
std::numeric_limits<T>::max() >
std::numeric_limits<uint32_t>::max()) {
MOZ_ASSERT(value <= UINT32_MAX);
}
return uint32_t(value);
}
static Maybe<T> fromUint32(uint32_t param) {
// Currently we use explicit conversion and don't range check.
return Some(T(param));
}
};
using ConvertBool = ConvertGeneric<bool>;
using ConvertSize = ConvertGeneric<size_t>;
using ConvertDouble = ConvertGeneric<double>;
struct ConvertTimes100 {
static uint32_t toUint32(double value) { return uint32_t(value * 100.0); }
static Maybe<double> fromUint32(uint32_t param) {
return Some(double(param) / 100.0);
}
};
struct ConvertNurseryBytes : ConvertSize {
static Maybe<size_t> fromUint32(uint32_t param) {
return Some(Nursery::roundSize(param));
}
};
struct ConvertKB {
static uint32_t toUint32(size_t value) { return value / 1024; }
static Maybe<size_t> fromUint32(uint32_t param) {
// Parameters which represent heap sizes in bytes are restricted to values
// which can be represented on 32 bit platforms.
CheckedInt<uint32_t> size = CheckedInt<uint32_t>(param) * 1024;
return size.isValid() ? Some(size_t(size.value())) : Nothing();
}
};
struct ConvertMB {
static uint32_t toUint32(size_t value) { return value / (1024 * 1024); }
static Maybe<size_t> fromUint32(uint32_t param) {
// Parameters which represent heap sizes in bytes are restricted to values
// which can be represented on 32 bit platforms.
CheckedInt<uint32_t> size = CheckedInt<uint32_t>(param) * 1024 * 1024;
return size.isValid() ? Some(size_t(size.value())) : Nothing();
}
};
struct ConvertMillis {
static uint32_t toUint32(TimeDuration value) {
return uint32_t(value.ToMilliseconds());
}
static Maybe<TimeDuration> fromUint32(uint32_t param) {
return Some(TimeDuration::FromMilliseconds(param));
}
};
struct ConvertSeconds {
static uint32_t toUint32(TimeDuration value) {
return uint32_t(value.ToSeconds());
}
static Maybe<TimeDuration> fromUint32(uint32_t param) {
return Some(TimeDuration::FromSeconds(param));
}
};
} // anonymous namespace
// Helper functions to check GC parameter values
template <typename T>
static bool NoCheck(T value) {
return true;
}
template <typename T>
static bool CheckNonZero(T value) {
return value != 0;
}
static bool CheckNurserySize(size_t bytes) {
return bytes >= SystemPageSize() && bytes <= MaxNurseryBytesParam;
}
static bool CheckHeapGrowth(double growth) {
return growth >= MinHeapGrowthFactor && growth <= MaxHeapGrowthFactor;
}
static bool CheckIncrementalLimit(double factor) {
return factor >= 1.0 && factor <= MaxHeapGrowthFactor;
}
static bool CheckNonZeroUnitRange(double value) {
return value > 0.0 && value <= 100.0;
}
GCSchedulingTunables::GCSchedulingTunables() {
#define INIT_TUNABLE_FIELD(key, type, name, convert, check, default) \
name##_ = default; \
MOZ_ASSERT(check(name##_));
FOR_EACH_GC_TUNABLE(INIT_TUNABLE_FIELD)
#undef INIT_TUNABLE_FIELD
checkInvariants();
}
uint32_t GCSchedulingTunables::getParameter(JSGCParamKey key) {
switch (key) {
#define GET_TUNABLE_FIELD(key, type, name, convert, check, default) \
case key: \
return convert::toUint32(name##_);
FOR_EACH_GC_TUNABLE(GET_TUNABLE_FIELD)
#undef GET_TUNABLE_FIELD
default:
MOZ_CRASH("Unknown parameter key");
}
}
bool GCSchedulingTunables::setParameter(JSGCParamKey key, uint32_t value) {
auto guard = mozilla::MakeScopeExit([this] { checkInvariants(); });
switch (key) {
#define SET_TUNABLE_FIELD(key, type, name, convert, check, default) \
case key: { \
Maybe<type> converted = convert::fromUint32(value); \
if (!converted || !check(converted.value())) { \
return false; \
} \
name##_ = converted.value(); \
break; \
}
FOR_EACH_GC_TUNABLE(SET_TUNABLE_FIELD)
#undef SET_TUNABLE_FIELD
default:
MOZ_CRASH("Unknown GC parameter.");
}
maintainInvariantsAfterUpdate(key);
return true;
}
void GCSchedulingTunables::resetParameter(JSGCParamKey key) {
auto guard = mozilla::MakeScopeExit([this] { checkInvariants(); });
switch (key) {
#define RESET_TUNABLE_FIELD(key, type, name, convert, check, default) \
case key: \
name##_ = default; \
MOZ_ASSERT(check(name##_)); \
break;
FOR_EACH_GC_TUNABLE(RESET_TUNABLE_FIELD)
#undef RESET_TUNABLE_FIELD
default:
MOZ_CRASH("Unknown GC parameter.");
}
maintainInvariantsAfterUpdate(key);
}
void GCSchedulingTunables::maintainInvariantsAfterUpdate(JSGCParamKey updated) {
// Check whether a change to parameter |updated| has broken an invariant in
// relation to another parameter. If it has, adjust that other parameter to
// restore the invariant.
switch (updated) {
case JSGC_MIN_NURSERY_BYTES:
if (gcMaxNurseryBytes_ < gcMinNurseryBytes_) {
gcMaxNurseryBytes_ = gcMinNurseryBytes_;
}
break;
case JSGC_MAX_NURSERY_BYTES:
if (gcMinNurseryBytes_ > gcMaxNurseryBytes_) {
gcMinNurseryBytes_ = gcMaxNurseryBytes_;
}
break;
case JSGC_SMALL_HEAP_SIZE_MAX:
if (smallHeapSizeMaxBytes_ >= largeHeapSizeMinBytes_) {
largeHeapSizeMinBytes_ = smallHeapSizeMaxBytes_ + 1;
}
break;
case JSGC_LARGE_HEAP_SIZE_MIN:
if (largeHeapSizeMinBytes_ <= smallHeapSizeMaxBytes_) {
smallHeapSizeMaxBytes_ = largeHeapSizeMinBytes_ - 1;
}
break;
case JSGC_HIGH_FREQUENCY_SMALL_HEAP_GROWTH:
if (highFrequencySmallHeapGrowth_ < highFrequencyLargeHeapGrowth_) {
highFrequencyLargeHeapGrowth_ = highFrequencySmallHeapGrowth_;
}
break;
case JSGC_HIGH_FREQUENCY_LARGE_HEAP_GROWTH:
if (highFrequencyLargeHeapGrowth_ > highFrequencySmallHeapGrowth_) {
highFrequencySmallHeapGrowth_ = highFrequencyLargeHeapGrowth_;
}
break;
case JSGC_SMALL_HEAP_INCREMENTAL_LIMIT:
if (smallHeapIncrementalLimit_ < largeHeapIncrementalLimit_) {
largeHeapIncrementalLimit_ = smallHeapIncrementalLimit_;
}
break;
case JSGC_LARGE_HEAP_INCREMENTAL_LIMIT:
if (largeHeapIncrementalLimit_ > smallHeapIncrementalLimit_) {
smallHeapIncrementalLimit_ = largeHeapIncrementalLimit_;
}
break;
default:
break;
}
}
void GCSchedulingTunables::checkInvariants() {
MOZ_ASSERT(gcMinNurseryBytes_ == Nursery::roundSize(gcMinNurseryBytes_));
MOZ_ASSERT(gcMaxNurseryBytes_ == Nursery::roundSize(gcMaxNurseryBytes_));
MOZ_ASSERT(gcMinNurseryBytes_ <= gcMaxNurseryBytes_);
MOZ_ASSERT(gcMinNurseryBytes_ >= SystemPageSize());
MOZ_ASSERT(gcMaxNurseryBytes_ <= MaxNurseryBytesParam);
MOZ_ASSERT(largeHeapSizeMinBytes_ > smallHeapSizeMaxBytes_);
MOZ_ASSERT(lowFrequencyHeapGrowth_ >= MinHeapGrowthFactor);
MOZ_ASSERT(lowFrequencyHeapGrowth_ <= MaxHeapGrowthFactor);
MOZ_ASSERT(highFrequencySmallHeapGrowth_ >= MinHeapGrowthFactor);
MOZ_ASSERT(highFrequencySmallHeapGrowth_ <= MaxHeapGrowthFactor);
MOZ_ASSERT(highFrequencyLargeHeapGrowth_ <= highFrequencySmallHeapGrowth_);
MOZ_ASSERT(highFrequencyLargeHeapGrowth_ >= MinHeapGrowthFactor);
MOZ_ASSERT(highFrequencySmallHeapGrowth_ <= MaxHeapGrowthFactor);
MOZ_ASSERT(smallHeapIncrementalLimit_ >= largeHeapIncrementalLimit_);
}
void GCSchedulingState::updateHighFrequencyModeOnGCStart(
JS::GCOptions options, const mozilla::TimeStamp& lastGCTime,
const mozilla::TimeStamp& currentTime,
const GCSchedulingTunables& tunables) {
// Set high frequency mode based on the time between collections.
TimeDuration timeSinceLastGC = currentTime - lastGCTime;
inHighFrequencyGCMode_ = !js::SupportDifferentialTesting() &&
options == JS::GCOptions::Normal &&
timeSinceLastGC < tunables.highFrequencyThreshold();
}
void GCSchedulingState::updateHighFrequencyModeOnSliceStart(
JS::GCOptions options, JS::GCReason reason) {
MOZ_ASSERT_IF(options != JS::GCOptions::Normal, !inHighFrequencyGCMode_);
// Additionally set high frequency mode for reasons that indicate that slices
// aren't being triggered often enough and the allocation rate is high.
if (options == JS::GCOptions::Normal &&
(reason == JS::GCReason::ALLOC_TRIGGER ||
reason == JS::GCReason::TOO_MUCH_MALLOC)) {
inHighFrequencyGCMode_ = true;
}
}
static constexpr size_t BytesPerMB = 1024 * 1024;
static constexpr double CollectionRateSmoothingFactor = 0.5;
static constexpr double AllocationRateSmoothingFactor = 0.5;
static double ExponentialMovingAverage(double prevAverage, double newData,
double smoothingFactor) {
MOZ_ASSERT(smoothingFactor > 0.0 && smoothingFactor <= 1.0);
return smoothingFactor * newData + (1.0 - smoothingFactor) * prevAverage;
}
void js::ZoneAllocator::updateCollectionRate(
mozilla::TimeDuration mainThreadGCTime, size_t initialBytesForAllZones) {
MOZ_ASSERT(initialBytesForAllZones != 0);
MOZ_ASSERT(gcHeapSize.initialBytes() <= initialBytesForAllZones);
double zoneFraction =
double(gcHeapSize.initialBytes()) / double(initialBytesForAllZones);
double zoneDuration = mainThreadGCTime.ToSeconds() * zoneFraction +
perZoneGCTime.ref().ToSeconds();
double collectionRate =
double(gcHeapSize.initialBytes()) / (zoneDuration * BytesPerMB);
if (!smoothedCollectionRate.ref()) {
smoothedCollectionRate = Some(collectionRate);
} else {
double prevRate = smoothedCollectionRate.ref().value();
smoothedCollectionRate = Some(ExponentialMovingAverage(
prevRate, collectionRate, CollectionRateSmoothingFactor));
}
}
void js::ZoneAllocator::updateAllocationRate(TimeDuration mutatorTime) {
// To get the total size allocated since the last collection we have to
// take account of how much memory got freed in the meantime.
size_t freedBytes = gcHeapSize.freedBytes();
size_t sizeIncludingFreedBytes = gcHeapSize.bytes() + freedBytes;
MOZ_ASSERT(prevGCHeapSize <= sizeIncludingFreedBytes);
size_t allocatedBytes = sizeIncludingFreedBytes - prevGCHeapSize;
double allocationRate =
double(allocatedBytes) / (mutatorTime.ToSeconds() * BytesPerMB);
if (!smoothedAllocationRate.ref()) {
smoothedAllocationRate = Some(allocationRate);
} else {
double prevRate = smoothedAllocationRate.ref().value();
smoothedAllocationRate = Some(ExponentialMovingAverage(
prevRate, allocationRate, AllocationRateSmoothingFactor));
}
gcHeapSize.clearFreedBytes();
prevGCHeapSize = gcHeapSize.bytes();
}
// GC thresholds may exceed the range of size_t on 32-bit platforms, so these
// are calculated using 64-bit integers and clamped.
static inline size_t ToClampedSize(uint64_t bytes) {
return std::min(bytes, uint64_t(SIZE_MAX));
}
void HeapThreshold::setIncrementalLimitFromStartBytes(
size_t retainedBytes, const GCSchedulingTunables& tunables) {
// Calculate the incremental limit for a heap based on its size and start
// threshold.
//
// This effectively classifies the heap size into small, medium or large, and
// uses the small heap incremental limit paramer, the large heap incremental
// limit parameter or an interpolation between them.
//
// The incremental limit is always set greater than the start threshold by at
// least the maximum nursery size to reduce the chance that tenuring a full
// nursery will send us straight into non-incremental collection.
MOZ_ASSERT(tunables.smallHeapIncrementalLimit() >=
tunables.largeHeapIncrementalLimit());
double factor = LinearInterpolate(double(retainedBytes),
double(tunables.smallHeapSizeMaxBytes()),
tunables.smallHeapIncrementalLimit(),
double(tunables.largeHeapSizeMinBytes()),
tunables.largeHeapIncrementalLimit());
uint64_t bytes =
std::max(uint64_t(double(startBytes_) * factor),
uint64_t(startBytes_) + tunables.gcMaxNurseryBytes());
incrementalLimitBytes_ = ToClampedSize(bytes);
MOZ_ASSERT(incrementalLimitBytes_ >= startBytes_);
// Maintain the invariant that the slice threshold is always less than the
// incremental limit when adjusting GC parameters.
if (hasSliceThreshold() && sliceBytes() > incrementalLimitBytes()) {
sliceBytes_ = incrementalLimitBytes();
}
}
size_t HeapThreshold::eagerAllocTrigger(bool highFrequencyGC) const {
double eagerTriggerFactor = highFrequencyGC
? HighFrequencyEagerAllocTriggerFactor
: LowFrequencyEagerAllocTriggerFactor;
return size_t(eagerTriggerFactor * double(startBytes()));
}
void HeapThreshold::setSliceThreshold(ZoneAllocator* zone,
const HeapSize& heapSize,
const GCSchedulingTunables& tunables,
bool waitingOnBGTask) {
// Set the allocation threshold at which to trigger the a GC slice in an
// ongoing incremental collection. This is used to ensure progress in
// allocation heavy code that may not return to the main event loop.
//
// The threshold is based on the JSGC_ZONE_ALLOC_DELAY_KB parameter, but this
// is reduced to increase the slice frequency as we approach the incremental
// limit, in the hope that we never reach it. If collector is waiting for a
// background task to complete, don't trigger any slices until we reach the
// urgent threshold.
size_t bytesRemaining = incrementalBytesRemaining(heapSize);
bool isUrgent = bytesRemaining < tunables.urgentThresholdBytes();
size_t delayBeforeNextSlice = tunables.zoneAllocDelayBytes();
if (isUrgent) {
double fractionRemaining =
double(bytesRemaining) / double(tunables.urgentThresholdBytes());
delayBeforeNextSlice =
size_t(double(delayBeforeNextSlice) * fractionRemaining);
MOZ_ASSERT(delayBeforeNextSlice <= tunables.zoneAllocDelayBytes());
} else if (waitingOnBGTask) {
delayBeforeNextSlice = bytesRemaining - tunables.urgentThresholdBytes();
}
sliceBytes_ = ToClampedSize(
std::min(uint64_t(heapSize.bytes()) + uint64_t(delayBeforeNextSlice),
uint64_t(incrementalLimitBytes_)));
}
size_t HeapThreshold::incrementalBytesRemaining(
const HeapSize& heapSize) const {
if (heapSize.bytes() >= incrementalLimitBytes_) {
return 0;
}
return incrementalLimitBytes_ - heapSize.bytes();
}
/* static */
double HeapThreshold::computeZoneHeapGrowthFactorForHeapSize(
size_t lastBytes, const GCSchedulingTunables& tunables,
const GCSchedulingState& state) {
// For small zones, our collection heuristics do not matter much: favor
// something simple in this case.
if (lastBytes < 1 * 1024 * 1024) {
return tunables.lowFrequencyHeapGrowth();
}
// The heap growth factor depends on the heap size after a GC and the GC
// frequency. If GC's are not triggering in rapid succession, use a lower
// threshold so that we will collect garbage sooner.
if (!state.inHighFrequencyGCMode()) {
return tunables.lowFrequencyHeapGrowth();
}
// For high frequency GCs we let the heap grow depending on whether we
// classify the heap as small, medium or large. There are parameters for small
// and large heap sizes and linear interpolation is used between them for
// medium sized heaps.
MOZ_ASSERT(tunables.smallHeapSizeMaxBytes() <=
tunables.largeHeapSizeMinBytes());
MOZ_ASSERT(tunables.highFrequencyLargeHeapGrowth() <=
tunables.highFrequencySmallHeapGrowth());
return LinearInterpolate(double(lastBytes),
double(tunables.smallHeapSizeMaxBytes()),
tunables.highFrequencySmallHeapGrowth(),
double(tunables.largeHeapSizeMinBytes()),
tunables.highFrequencyLargeHeapGrowth());
}
/* static */
size_t GCHeapThreshold::computeZoneTriggerBytes(
double growthFactor, size_t lastBytes,
const GCSchedulingTunables& tunables) {
size_t base = std::max(lastBytes, tunables.gcZoneAllocThresholdBase());
double trigger = double(base) * growthFactor;
double triggerMax =
double(tunables.gcMaxBytes()) / tunables.largeHeapIncrementalLimit();
return ToClampedSize(uint64_t(std::min(triggerMax, trigger)));
}
// Parameters for balanced heap limits computation.
// The W0 parameter. How much memory can be traversed in the minimum collection
// time.
static constexpr double BalancedHeapBaseMB = 5.0;
// The minimum heap limit. Do not constrain the heap to any less than this size.
static constexpr double MinBalancedHeapLimitMB = 10.0;
// The minimum amount of additional space to allow beyond the retained size.
static constexpr double MinBalancedHeadroomMB = 3.0;
// The maximum factor by which to expand the heap beyond the retained size.
static constexpr double MaxHeapGrowth = 3.0;
// The default allocation rate in MB/s allocated by the mutator to use before we
// have an estimate. Used to set the heap limit for zones that have not yet been
// collected.
static constexpr double DefaultAllocationRate = 0.0;
// The s0 parameter. The default collection rate in MB/s to use before we have
// an estimate. Used to set the heap limit for zones that have not yet been
// collected.
static constexpr double DefaultCollectionRate = 200.0;
double GCHeapThreshold::computeBalancedHeapLimit(
size_t lastBytes, double allocationRate, double collectionRate,
const GCSchedulingTunables& tunables) {
MOZ_ASSERT(tunables.balancedHeapLimitsEnabled());
// Optimal heap limits as described in https://arxiv.org/abs/2204.10455
double W = double(lastBytes) / BytesPerMB; // Retained size / MB.
double W0 = BalancedHeapBaseMB;
double d = tunables.heapGrowthFactor(); // Rearranged constant 'c'.
double g = allocationRate;
double s = collectionRate;
double f = d * sqrt((W + W0) * (g / s));
double M = W + std::min(f, MaxHeapGrowth * W);