1 // Copyright 2020 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/heap/cppgc/incremental-marking-schedule.h"
6
7 #include <cmath>
8
9 #include "src/heap/cppgc/globals.h"
10
11 namespace cppgc {
12 namespace internal {
13
14 // static
15 constexpr size_t IncrementalMarkingSchedule::kInvalidLastEstimatedLiveBytes;
16
17 const double IncrementalMarkingSchedule::kEstimatedMarkingTimeMs = 500.0;
18 const size_t IncrementalMarkingSchedule::kMinimumMarkedBytesPerIncrementalStep =
19 64 * kKB;
20
NotifyIncrementalMarkingStart()21 void IncrementalMarkingSchedule::NotifyIncrementalMarkingStart() {
22 DCHECK(incremental_marking_start_time_.IsNull());
23 incremental_marking_start_time_ = v8::base::TimeTicks::Now();
24 }
25
UpdateMutatorThreadMarkedBytes(size_t overall_marked_bytes)26 void IncrementalMarkingSchedule::UpdateMutatorThreadMarkedBytes(
27 size_t overall_marked_bytes) {
28 mutator_thread_marked_bytes_ = overall_marked_bytes;
29 }
30
AddConcurrentlyMarkedBytes(size_t marked_bytes)31 void IncrementalMarkingSchedule::AddConcurrentlyMarkedBytes(
32 size_t marked_bytes) {
33 concurrently_marked_bytes_.fetch_add(marked_bytes, std::memory_order_relaxed);
34 }
35
GetOverallMarkedBytes() const36 size_t IncrementalMarkingSchedule::GetOverallMarkedBytes() const {
37 return mutator_thread_marked_bytes_ + GetConcurrentlyMarkedBytes();
38 }
39
GetConcurrentlyMarkedBytes() const40 size_t IncrementalMarkingSchedule::GetConcurrentlyMarkedBytes() const {
41 return concurrently_marked_bytes_.load(std::memory_order_relaxed);
42 }
43
GetElapsedTimeInMs(v8::base::TimeTicks start_time)44 double IncrementalMarkingSchedule::GetElapsedTimeInMs(
45 v8::base::TimeTicks start_time) {
46 if (elapsed_time_for_testing_ != kNoSetElapsedTimeForTesting) {
47 double elapsed_time = elapsed_time_for_testing_;
48 elapsed_time_for_testing_ = kNoSetElapsedTimeForTesting;
49 return elapsed_time;
50 }
51 return (v8::base::TimeTicks::Now() - start_time).InMillisecondsF();
52 }
53
GetNextIncrementalStepDuration(size_t estimated_live_bytes)54 size_t IncrementalMarkingSchedule::GetNextIncrementalStepDuration(
55 size_t estimated_live_bytes) {
56 last_estimated_live_bytes_ = estimated_live_bytes;
57 DCHECK(!incremental_marking_start_time_.IsNull());
58 double elapsed_time_in_ms =
59 GetElapsedTimeInMs(incremental_marking_start_time_);
60 size_t actual_marked_bytes = GetOverallMarkedBytes();
61 size_t expected_marked_bytes = std::ceil(
62 estimated_live_bytes * elapsed_time_in_ms / kEstimatedMarkingTimeMs);
63 if (expected_marked_bytes < actual_marked_bytes) {
64 // Marking is ahead of schedule, incremental marking should do the minimum.
65 return kMinimumMarkedBytesPerIncrementalStep;
66 }
67 // Assuming marking will take |kEstimatedMarkingTime|, overall there will
68 // be |estimated_live_bytes| live bytes to mark, and that marking speed is
69 // constant, after |elapsed_time| the number of marked_bytes should be
70 // |estimated_live_bytes| * (|elapsed_time| / |kEstimatedMarkingTime|),
71 // denoted as |expected_marked_bytes|. If |actual_marked_bytes| is less,
72 // i.e. marking is behind schedule, incremental marking should help "catch
73 // up" by marking (|expected_marked_bytes| - |actual_marked_bytes|).
74 return std::max(kMinimumMarkedBytesPerIncrementalStep,
75 expected_marked_bytes - actual_marked_bytes);
76 }
77
78 constexpr double
79 IncrementalMarkingSchedule::kEphemeronPairsFlushingRatioIncrements;
ShouldFlushEphemeronPairs()80 bool IncrementalMarkingSchedule::ShouldFlushEphemeronPairs() {
81 DCHECK_NE(kInvalidLastEstimatedLiveBytes, last_estimated_live_bytes_);
82 if (GetOverallMarkedBytes() <
83 (ephemeron_pairs_flushing_ratio_target * last_estimated_live_bytes_))
84 return false;
85 ephemeron_pairs_flushing_ratio_target +=
86 kEphemeronPairsFlushingRatioIncrements;
87 return true;
88 }
89
90 } // namespace internal
91 } // namespace cppgc
92