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 DCHECK(!incremental_marking_start_time_.IsNull());
34 concurrently_marked_bytes_.fetch_add(marked_bytes, std::memory_order_relaxed);
35 }
36
GetOverallMarkedBytes() const37 size_t IncrementalMarkingSchedule::GetOverallMarkedBytes() const {
38 return mutator_thread_marked_bytes_ + GetConcurrentlyMarkedBytes();
39 }
40
GetConcurrentlyMarkedBytes() const41 size_t IncrementalMarkingSchedule::GetConcurrentlyMarkedBytes() const {
42 return concurrently_marked_bytes_.load(std::memory_order_relaxed);
43 }
44
GetElapsedTimeInMs(v8::base::TimeTicks start_time)45 double IncrementalMarkingSchedule::GetElapsedTimeInMs(
46 v8::base::TimeTicks start_time) {
47 if (elapsed_time_for_testing_ != kNoSetElapsedTimeForTesting) {
48 double elapsed_time = elapsed_time_for_testing_;
49 elapsed_time_for_testing_ = kNoSetElapsedTimeForTesting;
50 return elapsed_time;
51 }
52 return (v8::base::TimeTicks::Now() - start_time).InMillisecondsF();
53 }
54
GetNextIncrementalStepDuration(size_t estimated_live_bytes)55 size_t IncrementalMarkingSchedule::GetNextIncrementalStepDuration(
56 size_t estimated_live_bytes) {
57 last_estimated_live_bytes_ = estimated_live_bytes;
58 DCHECK(!incremental_marking_start_time_.IsNull());
59 double elapsed_time_in_ms =
60 GetElapsedTimeInMs(incremental_marking_start_time_);
61 size_t actual_marked_bytes = GetOverallMarkedBytes();
62 size_t expected_marked_bytes = std::ceil(
63 estimated_live_bytes * elapsed_time_in_ms / kEstimatedMarkingTimeMs);
64 if (expected_marked_bytes < actual_marked_bytes) {
65 // Marking is ahead of schedule, incremental marking should do the minimum.
66 return kMinimumMarkedBytesPerIncrementalStep;
67 }
68 // Assuming marking will take |kEstimatedMarkingTime|, overall there will
69 // be |estimated_live_bytes| live bytes to mark, and that marking speed is
70 // constant, after |elapsed_time| the number of marked_bytes should be
71 // |estimated_live_bytes| * (|elapsed_time| / |kEstimatedMarkingTime|),
72 // denoted as |expected_marked_bytes|. If |actual_marked_bytes| is less,
73 // i.e. marking is behind schedule, incremental marking should help "catch
74 // up" by marking (|expected_marked_bytes| - |actual_marked_bytes|).
75 return std::max(kMinimumMarkedBytesPerIncrementalStep,
76 expected_marked_bytes - actual_marked_bytes);
77 }
78
79 constexpr double
80 IncrementalMarkingSchedule::kEphemeronPairsFlushingRatioIncrements;
ShouldFlushEphemeronPairs()81 bool IncrementalMarkingSchedule::ShouldFlushEphemeronPairs() {
82 DCHECK_NE(kInvalidLastEstimatedLiveBytes, last_estimated_live_bytes_);
83 if (GetOverallMarkedBytes() <
84 (ephemeron_pairs_flushing_ratio_target * last_estimated_live_bytes_))
85 return false;
86 ephemeron_pairs_flushing_ratio_target +=
87 kEphemeronPairsFlushingRatioIncrements;
88 return true;
89 }
90
91 } // namespace internal
92 } // namespace cppgc
93