Bug Summary

File:out/../deps/v8/src/heap/base/worklist.h
Warning:line 400, column 7
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name marking-worklist.cc -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/home/maurizio/node-v18.6.0/out -resource-dir /usr/local/lib/clang/16.0.0 -D _GLIBCXX_USE_CXX11_ABI=1 -D NODE_OPENSSL_CONF_NAME=nodejs_conf -D NODE_OPENSSL_HAS_QUIC -D V8_GYP_BUILD -D V8_TYPED_ARRAY_MAX_SIZE_IN_HEAP=64 -D __STDC_FORMAT_MACROS -D OPENSSL_NO_PINSHARED -D OPENSSL_THREADS -D V8_TARGET_ARCH_X64 -D V8_HAVE_TARGET_OS -D V8_TARGET_OS_LINUX -D V8_EMBEDDER_STRING="-node.8" -D ENABLE_DISASSEMBLER -D V8_PROMISE_INTERNAL_FIELD_COUNT=1 -D V8_SHORT_BUILTIN_CALLS -D OBJECT_PRINT -D V8_INTL_SUPPORT -D V8_ATOMIC_OBJECT_FIELD_WRITES -D V8_ENABLE_LAZY_SOURCE_POSITIONS -D V8_USE_SIPHASH -D V8_SHARED_RO_HEAP -D V8_WIN64_UNWINDING_INFO -D V8_ENABLE_REGEXP_INTERPRETER_THREADED_DISPATCH -D V8_SNAPSHOT_COMPRESSION -D V8_ENABLE_WEBASSEMBLY -D V8_ENABLE_JAVASCRIPT_PROMISE_HOOKS -D V8_ALLOCATION_FOLDING -D V8_ALLOCATION_SITE_TRACKING -D V8_SCRIPTORMODULE_LEGACY_LIFETIME -D V8_ADVANCED_BIGINT_ALGORITHMS -D ICU_UTIL_DATA_IMPL=ICU_UTIL_DATA_STATIC -D UCONFIG_NO_SERVICE=1 -D U_ENABLE_DYLOAD=0 -D U_STATIC_IMPLEMENTATION=1 -D U_HAVE_STD_STRING=1 -D UCONFIG_NO_BREAK_ITERATION=0 -I ../deps/v8 -I ../deps/v8/include -I /home/maurizio/node-v18.6.0/out/Release/obj/gen/inspector-generated-output-root -I ../deps/v8/third_party/inspector_protocol -I /home/maurizio/node-v18.6.0/out/Release/obj/gen -I /home/maurizio/node-v18.6.0/out/Release/obj/gen/generate-bytecode-output-root -I ../deps/icu-small/source/i18n -I ../deps/icu-small/source/common -I ../deps/v8/third_party/zlib -I ../deps/v8/third_party/zlib/google -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8/x86_64-redhat-linux -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8/backward -internal-isystem /usr/local/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../x86_64-redhat-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Wno-unused-parameter -Wno-return-type -std=gnu++17 -fdeprecated-macro -fdebug-compilation-dir=/home/maurizio/node-v18.6.0/out -ferror-limit 19 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-08-22-142216-507842-1 -x c++ ../deps/v8/src/heap/marking-worklist.cc

../deps/v8/src/heap/marking-worklist.cc

→
1// Copyright 2019 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/marking-worklist.h"
6
7#include <algorithm>
8#include <cstddef>
9#include <map>
10
11#include "src/heap/cppgc-js/cpp-heap.h"
12#include "src/heap/cppgc-js/cpp-marking-state.h"
13#include "src/heap/marking-worklist-inl.h"
14#include "src/objects/heap-object-inl.h"
15#include "src/objects/heap-object.h"
16#include "src/objects/instance-type-inl.h"
17#include "src/objects/instance-type.h"
18#include "src/objects/map.h"
19#include "src/objects/objects-definitions.h"
20
21namespace v8 {
22namespace internal {
23
24MarkingWorklists::~MarkingWorklists() {
25 DCHECK(shared_.IsEmpty())((void) 0);
26 DCHECK(on_hold_.IsEmpty())((void) 0);
27 DCHECK(other_.IsEmpty())((void) 0);
28 DCHECK(worklists_.empty())((void) 0);
29 DCHECK(context_worklists_.empty())((void) 0);
30}
31
32void MarkingWorklists::Clear() {
33 shared_.Clear();
34 on_hold_.Clear();
35 wrapper_.Clear();
36 other_.Clear();
37 for (auto cw : context_worklists_) {
38 if (cw.context == kSharedContext || cw.context == kOtherContext) {
39 // These contexts were cleared above.
40 continue;
41 }
42 cw.worklist->Clear();
43 }
44 ReleaseContextWorklists();
45}
46
47void MarkingWorklists::Print() {
48 PrintWorklist("shared", &shared_);
49 PrintWorklist("on_hold", &on_hold_);
50}
51
52void MarkingWorklists::CreateContextWorklists(
53 const std::vector<Address>& contexts) {
54 DCHECK(worklists_.empty())((void) 0);
55 DCHECK(context_worklists_.empty())((void) 0);
56 if (contexts.empty()) return;
57 worklists_.reserve(contexts.size());
58 context_worklists_.reserve(contexts.size() + 2);
59 context_worklists_.push_back({kSharedContext, &shared_});
60 context_worklists_.push_back({kOtherContext, &other_});
61 for (Address context : contexts) {
62 MarkingWorklist* worklist = new MarkingWorklist();
63 worklists_.push_back(std::unique_ptr<MarkingWorklist>(worklist));
64 context_worklists_.push_back({context, worklist});
65 }
66}
67
68void MarkingWorklists::ReleaseContextWorklists() {
69 context_worklists_.clear();
70 worklists_.clear();
71}
72
73void MarkingWorklists::PrintWorklist(const char* worklist_name,
74 MarkingWorklist* worklist) {
75#ifdef DEBUG
76 std::map<InstanceType, int> count;
77 int total_count = 0;
78 worklist->Iterate([&count, &total_count](HeapObject obj) {
79 ++total_count;
80 count[obj.map().instance_type()]++;
81 });
82 std::vector<std::pair<int, InstanceType>> rank;
83 rank.reserve(count.size());
84 for (const auto& i : count) {
85 rank.emplace_back(i.second, i.first);
86 }
87 std::map<InstanceType, std::string> instance_type_name;
88#define INSTANCE_TYPE_NAME(name) instance_type_name[name] = #name;
89 INSTANCE_TYPE_LIST(INSTANCE_TYPE_NAME)INSTANCE_TYPE_NAME(INTERNALIZED_STRING_TYPE) INSTANCE_TYPE_NAME
(EXTERNAL_INTERNALIZED_STRING_TYPE) INSTANCE_TYPE_NAME(ONE_BYTE_INTERNALIZED_STRING_TYPE
) INSTANCE_TYPE_NAME(EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE
) INSTANCE_TYPE_NAME(UNCACHED_EXTERNAL_INTERNALIZED_STRING_TYPE
) INSTANCE_TYPE_NAME(UNCACHED_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE
) INSTANCE_TYPE_NAME(STRING_TYPE) INSTANCE_TYPE_NAME(CONS_STRING_TYPE
) INSTANCE_TYPE_NAME(EXTERNAL_STRING_TYPE) INSTANCE_TYPE_NAME
(SLICED_STRING_TYPE) INSTANCE_TYPE_NAME(THIN_STRING_TYPE) INSTANCE_TYPE_NAME
(ONE_BYTE_STRING_TYPE) INSTANCE_TYPE_NAME(CONS_ONE_BYTE_STRING_TYPE
) INSTANCE_TYPE_NAME(EXTERNAL_ONE_BYTE_STRING_TYPE) INSTANCE_TYPE_NAME
(SLICED_ONE_BYTE_STRING_TYPE) INSTANCE_TYPE_NAME(THIN_ONE_BYTE_STRING_TYPE
) INSTANCE_TYPE_NAME(UNCACHED_EXTERNAL_STRING_TYPE) INSTANCE_TYPE_NAME
(UNCACHED_EXTERNAL_ONE_BYTE_STRING_TYPE) INSTANCE_TYPE_NAME(SHARED_STRING_TYPE
) INSTANCE_TYPE_NAME(SHARED_THIN_STRING_TYPE) INSTANCE_TYPE_NAME
(SHARED_ONE_BYTE_STRING_TYPE) INSTANCE_TYPE_NAME(SHARED_THIN_ONE_BYTE_STRING_TYPE
) INSTANCE_TYPE_NAME(SYMBOL_TYPE) INSTANCE_TYPE_NAME(BIG_INT_BASE_TYPE
) INSTANCE_TYPE_NAME(HEAP_NUMBER_TYPE) INSTANCE_TYPE_NAME(ODDBALL_TYPE
) INSTANCE_TYPE_NAME(PROMISE_FULFILL_REACTION_JOB_TASK_TYPE) INSTANCE_TYPE_NAME
(PROMISE_REJECT_REACTION_JOB_TASK_TYPE) INSTANCE_TYPE_NAME(CALLABLE_TASK_TYPE
) INSTANCE_TYPE_NAME(CALLBACK_TASK_TYPE) INSTANCE_TYPE_NAME(PROMISE_RESOLVE_THENABLE_JOB_TASK_TYPE
) INSTANCE_TYPE_NAME(LOAD_HANDLER_TYPE) INSTANCE_TYPE_NAME(STORE_HANDLER_TYPE
) INSTANCE_TYPE_NAME(FUNCTION_TEMPLATE_INFO_TYPE) INSTANCE_TYPE_NAME
(OBJECT_TEMPLATE_INFO_TYPE) INSTANCE_TYPE_NAME(ACCESS_CHECK_INFO_TYPE
) INSTANCE_TYPE_NAME(ACCESSOR_INFO_TYPE) INSTANCE_TYPE_NAME(ACCESSOR_PAIR_TYPE
) INSTANCE_TYPE_NAME(ALIASED_ARGUMENTS_ENTRY_TYPE) INSTANCE_TYPE_NAME
(ALLOCATION_MEMENTO_TYPE) INSTANCE_TYPE_NAME(ALLOCATION_SITE_TYPE
) INSTANCE_TYPE_NAME(ARRAY_BOILERPLATE_DESCRIPTION_TYPE) INSTANCE_TYPE_NAME
(ASM_WASM_DATA_TYPE) INSTANCE_TYPE_NAME(ASYNC_GENERATOR_REQUEST_TYPE
) INSTANCE_TYPE_NAME(BREAK_POINT_TYPE) INSTANCE_TYPE_NAME(BREAK_POINT_INFO_TYPE
) INSTANCE_TYPE_NAME(CACHED_TEMPLATE_OBJECT_TYPE) INSTANCE_TYPE_NAME
(CALL_HANDLER_INFO_TYPE) INSTANCE_TYPE_NAME(CALL_SITE_INFO_TYPE
) INSTANCE_TYPE_NAME(CLASS_POSITIONS_TYPE) INSTANCE_TYPE_NAME
(DEBUG_INFO_TYPE) INSTANCE_TYPE_NAME(ENUM_CACHE_TYPE) INSTANCE_TYPE_NAME
(ERROR_STACK_DATA_TYPE) INSTANCE_TYPE_NAME(FEEDBACK_CELL_TYPE
) INSTANCE_TYPE_NAME(FUNCTION_TEMPLATE_RARE_DATA_TYPE) INSTANCE_TYPE_NAME
(INTERCEPTOR_INFO_TYPE) INSTANCE_TYPE_NAME(INTERPRETER_DATA_TYPE
) INSTANCE_TYPE_NAME(MODULE_REQUEST_TYPE) INSTANCE_TYPE_NAME(
PROMISE_CAPABILITY_TYPE) INSTANCE_TYPE_NAME(PROMISE_ON_STACK_TYPE
) INSTANCE_TYPE_NAME(PROMISE_REACTION_TYPE) INSTANCE_TYPE_NAME
(PROPERTY_DESCRIPTOR_OBJECT_TYPE) INSTANCE_TYPE_NAME(PROTOTYPE_INFO_TYPE
) INSTANCE_TYPE_NAME(REG_EXP_BOILERPLATE_DESCRIPTION_TYPE) INSTANCE_TYPE_NAME
(SCRIPT_TYPE) INSTANCE_TYPE_NAME(SCRIPT_OR_MODULE_TYPE) INSTANCE_TYPE_NAME
(SOURCE_TEXT_MODULE_INFO_ENTRY_TYPE) INSTANCE_TYPE_NAME(STACK_FRAME_INFO_TYPE
) INSTANCE_TYPE_NAME(TEMPLATE_OBJECT_DESCRIPTION_TYPE) INSTANCE_TYPE_NAME
(TUPLE2_TYPE) INSTANCE_TYPE_NAME(WASM_CONTINUATION_OBJECT_TYPE
) INSTANCE_TYPE_NAME(WASM_EXCEPTION_TAG_TYPE) INSTANCE_TYPE_NAME
(WASM_INDIRECT_FUNCTION_TABLE_TYPE) INSTANCE_TYPE_NAME(FIXED_ARRAY_TYPE
) INSTANCE_TYPE_NAME(HASH_TABLE_TYPE) INSTANCE_TYPE_NAME(EPHEMERON_HASH_TABLE_TYPE
) INSTANCE_TYPE_NAME(GLOBAL_DICTIONARY_TYPE) INSTANCE_TYPE_NAME
(NAME_DICTIONARY_TYPE) INSTANCE_TYPE_NAME(NAME_TO_INDEX_HASH_TABLE_TYPE
) INSTANCE_TYPE_NAME(NUMBER_DICTIONARY_TYPE) INSTANCE_TYPE_NAME
(ORDERED_HASH_MAP_TYPE) INSTANCE_TYPE_NAME(ORDERED_HASH_SET_TYPE
) INSTANCE_TYPE_NAME(ORDERED_NAME_DICTIONARY_TYPE) INSTANCE_TYPE_NAME
(REGISTERED_SYMBOL_TABLE_TYPE) INSTANCE_TYPE_NAME(SIMPLE_NUMBER_DICTIONARY_TYPE
) INSTANCE_TYPE_NAME(CLOSURE_FEEDBACK_CELL_ARRAY_TYPE) INSTANCE_TYPE_NAME
(OBJECT_BOILERPLATE_DESCRIPTION_TYPE) INSTANCE_TYPE_NAME(SCRIPT_CONTEXT_TABLE_TYPE
) INSTANCE_TYPE_NAME(BYTE_ARRAY_TYPE) INSTANCE_TYPE_NAME(BYTECODE_ARRAY_TYPE
) INSTANCE_TYPE_NAME(FIXED_DOUBLE_ARRAY_TYPE) INSTANCE_TYPE_NAME
(INTERNAL_CLASS_WITH_SMI_ELEMENTS_TYPE) INSTANCE_TYPE_NAME(SLOPPY_ARGUMENTS_ELEMENTS_TYPE
) INSTANCE_TYPE_NAME(TURBOFAN_BITSET_TYPE_TYPE) INSTANCE_TYPE_NAME
(TURBOFAN_HEAP_CONSTANT_TYPE_TYPE) INSTANCE_TYPE_NAME(TURBOFAN_OTHER_NUMBER_CONSTANT_TYPE_TYPE
) INSTANCE_TYPE_NAME(TURBOFAN_RANGE_TYPE_TYPE) INSTANCE_TYPE_NAME
(TURBOFAN_UNION_TYPE_TYPE) INSTANCE_TYPE_NAME(FOREIGN_TYPE) INSTANCE_TYPE_NAME
(WASM_INTERNAL_FUNCTION_TYPE) INSTANCE_TYPE_NAME(WASM_TYPE_INFO_TYPE
) INSTANCE_TYPE_NAME(AWAIT_CONTEXT_TYPE) INSTANCE_TYPE_NAME(BLOCK_CONTEXT_TYPE
) INSTANCE_TYPE_NAME(CATCH_CONTEXT_TYPE) INSTANCE_TYPE_NAME(DEBUG_EVALUATE_CONTEXT_TYPE
) INSTANCE_TYPE_NAME(EVAL_CONTEXT_TYPE) INSTANCE_TYPE_NAME(FUNCTION_CONTEXT_TYPE
) INSTANCE_TYPE_NAME(MODULE_CONTEXT_TYPE) INSTANCE_TYPE_NAME(
NATIVE_CONTEXT_TYPE) INSTANCE_TYPE_NAME(SCRIPT_CONTEXT_TYPE) INSTANCE_TYPE_NAME
(WITH_CONTEXT_TYPE) INSTANCE_TYPE_NAME(UNCOMPILED_DATA_WITH_PREPARSE_DATA_TYPE
) INSTANCE_TYPE_NAME(UNCOMPILED_DATA_WITH_PREPARSE_DATA_AND_JOB_TYPE
) INSTANCE_TYPE_NAME(UNCOMPILED_DATA_WITHOUT_PREPARSE_DATA_TYPE
) INSTANCE_TYPE_NAME(UNCOMPILED_DATA_WITHOUT_PREPARSE_DATA_WITH_JOB_TYPE
) INSTANCE_TYPE_NAME(WASM_FUNCTION_DATA_TYPE) INSTANCE_TYPE_NAME
(WASM_CAPI_FUNCTION_DATA_TYPE) INSTANCE_TYPE_NAME(WASM_EXPORTED_FUNCTION_DATA_TYPE
) INSTANCE_TYPE_NAME(WASM_JS_FUNCTION_DATA_TYPE) INSTANCE_TYPE_NAME
(EXPORTED_SUB_CLASS_BASE_TYPE) INSTANCE_TYPE_NAME(EXPORTED_SUB_CLASS_TYPE
) INSTANCE_TYPE_NAME(EXPORTED_SUB_CLASS2_TYPE) INSTANCE_TYPE_NAME
(SMALL_ORDERED_HASH_MAP_TYPE) INSTANCE_TYPE_NAME(SMALL_ORDERED_HASH_SET_TYPE
) INSTANCE_TYPE_NAME(SMALL_ORDERED_NAME_DICTIONARY_TYPE) INSTANCE_TYPE_NAME
(ABSTRACT_INTERNAL_CLASS_SUBCLASS1_TYPE) INSTANCE_TYPE_NAME(ABSTRACT_INTERNAL_CLASS_SUBCLASS2_TYPE
) INSTANCE_TYPE_NAME(DESCRIPTOR_ARRAY_TYPE) INSTANCE_TYPE_NAME
(STRONG_DESCRIPTOR_ARRAY_TYPE) INSTANCE_TYPE_NAME(SOURCE_TEXT_MODULE_TYPE
) INSTANCE_TYPE_NAME(SYNTHETIC_MODULE_TYPE) INSTANCE_TYPE_NAME
(WEAK_FIXED_ARRAY_TYPE) INSTANCE_TYPE_NAME(TRANSITION_ARRAY_TYPE
) INSTANCE_TYPE_NAME(CELL_TYPE) INSTANCE_TYPE_NAME(CODE_TYPE)
INSTANCE_TYPE_NAME(CODE_DATA_CONTAINER_TYPE) INSTANCE_TYPE_NAME
(COVERAGE_INFO_TYPE) INSTANCE_TYPE_NAME(EMBEDDER_DATA_ARRAY_TYPE
) INSTANCE_TYPE_NAME(FEEDBACK_METADATA_TYPE) INSTANCE_TYPE_NAME
(FEEDBACK_VECTOR_TYPE) INSTANCE_TYPE_NAME(FILLER_TYPE) INSTANCE_TYPE_NAME
(FREE_SPACE_TYPE) INSTANCE_TYPE_NAME(INTERNAL_CLASS_TYPE) INSTANCE_TYPE_NAME
(INTERNAL_CLASS_WITH_STRUCT_ELEMENTS_TYPE) INSTANCE_TYPE_NAME
(MAP_TYPE) INSTANCE_TYPE_NAME(MEGA_DOM_HANDLER_TYPE) INSTANCE_TYPE_NAME
(ON_HEAP_BASIC_BLOCK_PROFILER_DATA_TYPE) INSTANCE_TYPE_NAME(PREPARSE_DATA_TYPE
) INSTANCE_TYPE_NAME(PROPERTY_ARRAY_TYPE) INSTANCE_TYPE_NAME(
PROPERTY_CELL_TYPE) INSTANCE_TYPE_NAME(SCOPE_INFO_TYPE) INSTANCE_TYPE_NAME
(SHARED_FUNCTION_INFO_TYPE) INSTANCE_TYPE_NAME(SMI_BOX_TYPE) INSTANCE_TYPE_NAME
(SMI_PAIR_TYPE) INSTANCE_TYPE_NAME(SORT_STATE_TYPE) INSTANCE_TYPE_NAME
(SWISS_NAME_DICTIONARY_TYPE) INSTANCE_TYPE_NAME(WASM_API_FUNCTION_REF_TYPE
) INSTANCE_TYPE_NAME(WASM_ON_FULFILLED_DATA_TYPE) INSTANCE_TYPE_NAME
(WEAK_ARRAY_LIST_TYPE) INSTANCE_TYPE_NAME(WEAK_CELL_TYPE) INSTANCE_TYPE_NAME
(WASM_ARRAY_TYPE) INSTANCE_TYPE_NAME(WASM_STRUCT_TYPE) INSTANCE_TYPE_NAME
(JS_PROXY_TYPE) INSTANCE_TYPE_NAME(JS_OBJECT_TYPE) INSTANCE_TYPE_NAME
(JS_GLOBAL_OBJECT_TYPE) INSTANCE_TYPE_NAME(JS_GLOBAL_PROXY_TYPE
) INSTANCE_TYPE_NAME(JS_MODULE_NAMESPACE_TYPE) INSTANCE_TYPE_NAME
(JS_SPECIAL_API_OBJECT_TYPE) INSTANCE_TYPE_NAME(JS_PRIMITIVE_WRAPPER_TYPE
) INSTANCE_TYPE_NAME(JS_API_OBJECT_TYPE) INSTANCE_TYPE_NAME(JS_LAST_DUMMY_API_OBJECT_TYPE
) INSTANCE_TYPE_NAME(JS_DATA_VIEW_TYPE) INSTANCE_TYPE_NAME(JS_TYPED_ARRAY_TYPE
) INSTANCE_TYPE_NAME(JS_ARRAY_BUFFER_TYPE) INSTANCE_TYPE_NAME
(JS_PROMISE_TYPE) INSTANCE_TYPE_NAME(JS_BOUND_FUNCTION_TYPE) INSTANCE_TYPE_NAME
(JS_WRAPPED_FUNCTION_TYPE) INSTANCE_TYPE_NAME(JS_FUNCTION_TYPE
) INSTANCE_TYPE_NAME(BIGINT64_TYPED_ARRAY_CONSTRUCTOR_TYPE) INSTANCE_TYPE_NAME
(BIGUINT64_TYPED_ARRAY_CONSTRUCTOR_TYPE) INSTANCE_TYPE_NAME(FLOAT32_TYPED_ARRAY_CONSTRUCTOR_TYPE
) INSTANCE_TYPE_NAME(FLOAT64_TYPED_ARRAY_CONSTRUCTOR_TYPE) INSTANCE_TYPE_NAME
(INT16_TYPED_ARRAY_CONSTRUCTOR_TYPE) INSTANCE_TYPE_NAME(INT32_TYPED_ARRAY_CONSTRUCTOR_TYPE
) INSTANCE_TYPE_NAME(INT8_TYPED_ARRAY_CONSTRUCTOR_TYPE) INSTANCE_TYPE_NAME
(UINT16_TYPED_ARRAY_CONSTRUCTOR_TYPE) INSTANCE_TYPE_NAME(UINT32_TYPED_ARRAY_CONSTRUCTOR_TYPE
) INSTANCE_TYPE_NAME(UINT8_CLAMPED_TYPED_ARRAY_CONSTRUCTOR_TYPE
) INSTANCE_TYPE_NAME(UINT8_TYPED_ARRAY_CONSTRUCTOR_TYPE) INSTANCE_TYPE_NAME
(JS_ARRAY_CONSTRUCTOR_TYPE) INSTANCE_TYPE_NAME(JS_PROMISE_CONSTRUCTOR_TYPE
) INSTANCE_TYPE_NAME(JS_REG_EXP_CONSTRUCTOR_TYPE) INSTANCE_TYPE_NAME
(JS_CLASS_CONSTRUCTOR_TYPE) INSTANCE_TYPE_NAME(JS_ARRAY_ITERATOR_PROTOTYPE_TYPE
) INSTANCE_TYPE_NAME(JS_ITERATOR_PROTOTYPE_TYPE) INSTANCE_TYPE_NAME
(JS_MAP_ITERATOR_PROTOTYPE_TYPE) INSTANCE_TYPE_NAME(JS_OBJECT_PROTOTYPE_TYPE
) INSTANCE_TYPE_NAME(JS_PROMISE_PROTOTYPE_TYPE) INSTANCE_TYPE_NAME
(JS_REG_EXP_PROTOTYPE_TYPE) INSTANCE_TYPE_NAME(JS_SET_ITERATOR_PROTOTYPE_TYPE
) INSTANCE_TYPE_NAME(JS_SET_PROTOTYPE_TYPE) INSTANCE_TYPE_NAME
(JS_STRING_ITERATOR_PROTOTYPE_TYPE) INSTANCE_TYPE_NAME(JS_TYPED_ARRAY_PROTOTYPE_TYPE
) INSTANCE_TYPE_NAME(JS_MAP_KEY_ITERATOR_TYPE) INSTANCE_TYPE_NAME
(JS_MAP_KEY_VALUE_ITERATOR_TYPE) INSTANCE_TYPE_NAME(JS_MAP_VALUE_ITERATOR_TYPE
) INSTANCE_TYPE_NAME(JS_SET_KEY_VALUE_ITERATOR_TYPE) INSTANCE_TYPE_NAME
(JS_SET_VALUE_ITERATOR_TYPE) INSTANCE_TYPE_NAME(JS_GENERATOR_OBJECT_TYPE
) INSTANCE_TYPE_NAME(JS_ASYNC_FUNCTION_OBJECT_TYPE) INSTANCE_TYPE_NAME
(JS_ASYNC_GENERATOR_OBJECT_TYPE) INSTANCE_TYPE_NAME(JS_MAP_TYPE
) INSTANCE_TYPE_NAME(JS_SET_TYPE) INSTANCE_TYPE_NAME(JS_WEAK_MAP_TYPE
) INSTANCE_TYPE_NAME(JS_WEAK_SET_TYPE) INSTANCE_TYPE_NAME(JS_ARGUMENTS_OBJECT_TYPE
) INSTANCE_TYPE_NAME(JS_ARRAY_TYPE) INSTANCE_TYPE_NAME(JS_ARRAY_ITERATOR_TYPE
) INSTANCE_TYPE_NAME(JS_ASYNC_FROM_SYNC_ITERATOR_TYPE) INSTANCE_TYPE_NAME
(JS_COLLATOR_TYPE) INSTANCE_TYPE_NAME(JS_CONTEXT_EXTENSION_OBJECT_TYPE
) INSTANCE_TYPE_NAME(JS_DATE_TYPE) INSTANCE_TYPE_NAME(JS_DATE_TIME_FORMAT_TYPE
) INSTANCE_TYPE_NAME(JS_DISPLAY_NAMES_TYPE) INSTANCE_TYPE_NAME
(JS_ERROR_TYPE) INSTANCE_TYPE_NAME(JS_EXTERNAL_OBJECT_TYPE) INSTANCE_TYPE_NAME
(JS_FINALIZATION_REGISTRY_TYPE) INSTANCE_TYPE_NAME(JS_LIST_FORMAT_TYPE
) INSTANCE_TYPE_NAME(JS_LOCALE_TYPE) INSTANCE_TYPE_NAME(JS_MESSAGE_OBJECT_TYPE
) INSTANCE_TYPE_NAME(JS_NUMBER_FORMAT_TYPE) INSTANCE_TYPE_NAME
(JS_PLURAL_RULES_TYPE) INSTANCE_TYPE_NAME(JS_REG_EXP_TYPE) INSTANCE_TYPE_NAME
(JS_REG_EXP_STRING_ITERATOR_TYPE) INSTANCE_TYPE_NAME(JS_RELATIVE_TIME_FORMAT_TYPE
) INSTANCE_TYPE_NAME(JS_SEGMENT_ITERATOR_TYPE) INSTANCE_TYPE_NAME
(JS_SEGMENTER_TYPE) INSTANCE_TYPE_NAME(JS_SEGMENTS_TYPE) INSTANCE_TYPE_NAME
(JS_SHADOW_REALM_TYPE) INSTANCE_TYPE_NAME(JS_SHARED_STRUCT_TYPE
) INSTANCE_TYPE_NAME(JS_STRING_ITERATOR_TYPE) INSTANCE_TYPE_NAME
(JS_TEMPORAL_CALENDAR_TYPE) INSTANCE_TYPE_NAME(JS_TEMPORAL_DURATION_TYPE
) INSTANCE_TYPE_NAME(JS_TEMPORAL_INSTANT_TYPE) INSTANCE_TYPE_NAME
(JS_TEMPORAL_PLAIN_DATE_TYPE) INSTANCE_TYPE_NAME(JS_TEMPORAL_PLAIN_DATE_TIME_TYPE
) INSTANCE_TYPE_NAME(JS_TEMPORAL_PLAIN_MONTH_DAY_TYPE) INSTANCE_TYPE_NAME
(JS_TEMPORAL_PLAIN_TIME_TYPE) INSTANCE_TYPE_NAME(JS_TEMPORAL_PLAIN_YEAR_MONTH_TYPE
) INSTANCE_TYPE_NAME(JS_TEMPORAL_TIME_ZONE_TYPE) INSTANCE_TYPE_NAME
(JS_TEMPORAL_ZONED_DATE_TIME_TYPE) INSTANCE_TYPE_NAME(JS_V8_BREAK_ITERATOR_TYPE
) INSTANCE_TYPE_NAME(JS_WEAK_REF_TYPE) INSTANCE_TYPE_NAME(WASM_GLOBAL_OBJECT_TYPE
) INSTANCE_TYPE_NAME(WASM_INSTANCE_OBJECT_TYPE) INSTANCE_TYPE_NAME
(WASM_MEMORY_OBJECT_TYPE) INSTANCE_TYPE_NAME(WASM_MODULE_OBJECT_TYPE
) INSTANCE_TYPE_NAME(WASM_SUSPENDER_OBJECT_TYPE) INSTANCE_TYPE_NAME
(WASM_TABLE_OBJECT_TYPE) INSTANCE_TYPE_NAME(WASM_TAG_OBJECT_TYPE
) INSTANCE_TYPE_NAME(WASM_VALUE_OBJECT_TYPE)
90#undef INSTANCE_TYPE_NAME
91 std::sort(rank.begin(), rank.end(),
92 std::greater<std::pair<int, InstanceType>>());
93 PrintF("Worklist %s: %d\n", worklist_name, total_count);
94 for (auto i : rank) {
95 PrintF(" [%s]: %d\n", instance_type_name[i.second].c_str(), i.first);
96 }
97#endif
98}
99
100constexpr Address MarkingWorklists::Local::kSharedContext;
101constexpr Address MarkingWorklists::Local::kOtherContext;
102constexpr std::nullptr_t MarkingWorklists::Local::kNoCppMarkingState;
103
104MarkingWorklists::Local::Local(
105 MarkingWorklists* global,
106 std::unique_ptr<CppMarkingState> cpp_marking_state)
107 : on_hold_(global->on_hold()),
108 wrapper_(global->wrapper()),
109 is_per_context_mode_(false),
110 cpp_marking_state_(std::move(cpp_marking_state)) {
111 if (global->context_worklists().empty()) {
112 MarkingWorklist::Local shared(global->shared());
113 active_ = std::move(shared);
114 active_context_ = kSharedContext;
115 active_owner_ = nullptr;
116 } else {
117 is_per_context_mode_ = true;
118 worklist_by_context_.reserve(global->context_worklists().size());
119 for (auto& cw : global->context_worklists()) {
120 worklist_by_context_[cw.context] =
121 std::make_unique<MarkingWorklist::Local>(cw.worklist);
122 }
123 active_owner_ = worklist_by_context_[kSharedContext].get();
124 active_ = std::move(*active_owner_);
125 active_context_ = kSharedContext;
126 }
127}
128
129MarkingWorklists::Local::~Local() {
130 DCHECK(active_.IsLocalEmpty())((void) 0);
131 if (is_per_context_mode_) {
132 for (auto& cw : worklist_by_context_) {
133 if (cw.first != active_context_) {
134 DCHECK(cw.second->IsLocalEmpty())((void) 0);
135 }
136 }
137 }
138}
139
140void MarkingWorklists::Local::Publish() {
141 active_.Publish();
142 on_hold_.Publish();
143 wrapper_.Publish();
144 if (is_per_context_mode_) {
145 for (auto& cw : worklist_by_context_) {
146 if (cw.first != active_context_) {
147 cw.second->Publish();
148 }
149 }
150 }
151 PublishWrapper();
152}
153
154bool MarkingWorklists::Local::IsEmpty() {
155 // This function checks the on_hold_ worklist, so it works only for the main
156 // thread.
157 if (!active_.IsLocalEmpty() || !on_hold_.IsLocalEmpty() ||
158 !active_.IsGlobalEmpty() || !on_hold_.IsGlobalEmpty()) {
159 return false;
160 }
161 if (!is_per_context_mode_) {
162 return true;
163 }
164 for (auto& cw : worklist_by_context_) {
165 if (cw.first != active_context_ &&
166 !(cw.second->IsLocalEmpty() && cw.second->IsGlobalEmpty())) {
167 SwitchToContext(cw.first, cw.second.get());
168 return false;
169 }
170 }
171 return true;
172}
173
174bool MarkingWorklists::Local::IsWrapperEmpty() const {
175 if (cpp_marking_state_) {
176 DCHECK(wrapper_.IsLocalAndGlobalEmpty())((void) 0);
177 return cpp_marking_state_->IsLocalEmpty();
178 }
179 return wrapper_.IsLocalAndGlobalEmpty();
180}
181
182void MarkingWorklists::Local::ShareWork() {
183 if (!active_.IsLocalEmpty() && active_.IsGlobalEmpty()) {
184 active_.Publish();
185 }
186 if (is_per_context_mode_ && active_context_ != kSharedContext) {
187 MarkingWorklist::Local* shared = worklist_by_context_[kSharedContext].get();
188 if (!shared->IsLocalEmpty() && shared->IsGlobalEmpty()) {
189 shared->Publish();
190 }
191 }
192}
193
194void MarkingWorklists::Local::MergeOnHold() {
195 MarkingWorklist::Local* shared =
196 active_context_ == kSharedContext
197 ? &active_
198 : worklist_by_context_[kSharedContext].get();
199 shared->Merge(&on_hold_);
200}
201
202bool MarkingWorklists::Local::PopContext(HeapObject* object) {
203 DCHECK(is_per_context_mode_)((void) 0);
204 // As an optimization we first check only the local segments to avoid locks.
205 for (auto& cw : worklist_by_context_) {
206 if (cw.first != active_context_ && !cw.second->IsLocalEmpty()) {
1
Assuming field 'first' is not equal to field 'active_context_'
→
2
←
Taking true branch
→
207 SwitchToContext(cw.first, cw.second.get());
3
←
Calling 'Local::SwitchToContext'
→
9
←
Returning from 'Local::SwitchToContext'
→
208 return active_.Pop(object);
10
←
Calling 'Local::Pop'
→
209 }
210 }
211 // All local segments are empty. Check global segments.
212 for (auto& cw : worklist_by_context_) {
213 if (cw.first != active_context_ && cw.second->Pop(object)) {
214 SwitchToContext(cw.first, cw.second.get());
215 return true;
216 }
217 }
218 // All worklists are empty. Switch to the default shared worklist.
219 SwitchToContext(kSharedContext);
220 return false;
221}
222
223Address MarkingWorklists::Local::SwitchToContextSlow(Address context) {
224 const auto& it = worklist_by_context_.find(context);
225 if (V8_UNLIKELY(it == worklist_by_context_.end())(__builtin_expect(!!(it == worklist_by_context_.end()), 0))) {
226 // This context was created during marking or is not being measured,
227 // so we don't have a specific worklist for it.
228 SwitchToContext(kOtherContext, worklist_by_context_[kOtherContext].get());
229 } else {
230 SwitchToContext(it->first, it->second.get());
231 }
232 return active_context_;
233}
234
235} // namespace internal
236} // namespace v8
←

../deps/v8/src/heap/marking-worklist-inl.h

→
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#ifndef V8_HEAP_MARKING_WORKLIST_INL_H_
5#define V8_HEAP_MARKING_WORKLIST_INL_H_
6
7#include <unordered_map>
8
9#include "src/heap/cppgc-js/cpp-marking-state-inl.h"
10#include "src/heap/marking-worklist.h"
11#include "src/objects/embedder-data-slot.h"
12#include "src/objects/js-objects-inl.h"
13
14namespace v8 {
15namespace internal {
16
17template <typename Callback>
18void MarkingWorklists::Update(Callback callback) {
19 shared_.Update(callback);
20 on_hold_.Update(callback);
21 wrapper_.Update(callback);
22 other_.Update(callback);
23 for (auto cw : context_worklists_) {
24 if (cw.context == kSharedContext || cw.context == kOtherContext) {
25 // These contexts were updated above.
26 continue;
27 }
28 cw.worklist->Update(callback);
29 }
30}
31
32void MarkingWorklists::Local::Push(HeapObject object) { active_.Push(object); }
33
34bool MarkingWorklists::Local::Pop(HeapObject* object) {
35 if (active_.Pop(object)) return true;
36 if (!is_per_context_mode_) return false;
37 // The active worklist is empty. Find any other non-empty worklist and
38 // switch the active worklist to it.
39 return PopContext(object);
40}
41
42void MarkingWorklists::Local::PushOnHold(HeapObject object) {
43 on_hold_.Push(object);
44}
45
46bool MarkingWorklists::Local::PopOnHold(HeapObject* object) {
47 return on_hold_.Pop(object);
48}
49
50bool MarkingWorklists::Local::SupportsExtractWrapper() {
51 return cpp_marking_state_.get();
52}
53
54bool MarkingWorklists::Local::ExtractWrapper(Map map, JSObject object,
55 WrapperSnapshot& snapshot) {
56 DCHECK_NOT_NULL(cpp_marking_state_)((void) 0);
57 return cpp_marking_state_->ExtractEmbedderDataSnapshot(map, object, snapshot);
58}
59
60void MarkingWorklists::Local::PushExtractedWrapper(
61 const WrapperSnapshot& snapshot) {
62 DCHECK_NOT_NULL(cpp_marking_state_)((void) 0);
63 cpp_marking_state_->MarkAndPush(snapshot);
64}
65
66void MarkingWorklists::Local::PushWrapper(HeapObject object) {
67 DCHECK_NULL(cpp_marking_state_)((void) 0);
68 wrapper_.Push(object);
69}
70
71bool MarkingWorklists::Local::PopWrapper(HeapObject* object) {
72 DCHECK_NULL(cpp_marking_state_)((void) 0);
73 return wrapper_.Pop(object);
74}
75
76Address MarkingWorklists::Local::SwitchToContext(Address context) {
77 if (context == active_context_) return context;
78 return SwitchToContextSlow(context);
79}
80
81Address MarkingWorklists::Local::SwitchToShared() {
82 return SwitchToContext(kSharedContext);
83}
84
85void MarkingWorklists::Local::SwitchToContext(
86 Address context, MarkingWorklist::Local* worklist) {
87 // Save the current worklist.
88 *active_owner_ = std::move(active_);
4
←
Calling move assignment operator for 'Local'
→
8
←
Returning from move assignment operator for 'Local'
→
89 // Switch to the new worklist.
90 active_owner_ = worklist;
91 active_ = std::move(*worklist);
92 active_context_ = context;
93}
94
95bool MarkingWorklists::Local::PublishWrapper() {
96 if (!cpp_marking_state_) return false;
97 cpp_marking_state_->Publish();
98 return true;
99}
100
101} // namespace internal
102} // namespace v8
103
104#endif // V8_HEAP_MARKING_WORKLIST_INL_H_
←

../deps/v8/src/heap/base/worklist.h

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#ifndef V8_HEAP_BASE_WORKLIST_H_
6#define V8_HEAP_BASE_WORKLIST_H_
7
8#include <cstddef>
9#include <utility>
10
11#include "src/base/atomic-utils.h"
12#include "src/base/logging.h"
13#include "src/base/platform/mutex.h"
14#include "testing/gtest/include/gtest/gtest_prod.h" // nogncheck
15
16namespace heap {
17namespace base {
18
19namespace internal {
20class V8_EXPORT_PRIVATE SegmentBase {
21 public:
22 static SegmentBase* GetSentinelSegmentAddress();
23
24 explicit SegmentBase(uint16_t capacity) : capacity_(capacity) {}
25
26 size_t Size() const { return index_; }
27 bool IsEmpty() const { return index_ == 0; }
28 bool IsFull() const { return index_ == capacity_; }
29 void Clear() { index_ = 0; }
30
31 protected:
32 const uint16_t capacity_;
33 uint16_t index_ = 0;
34};
35} // namespace internal
36
37// A global marking worklist that is similar the existing Worklist
38// but does not reserve space and keep track of the local segments.
39// Eventually this will replace Worklist after all its current uses
40// are migrated.
41template <typename EntryType, uint16_t SegmentSize>
42class Worklist {
43 public:
44 static const int kSegmentSize = SegmentSize;
45 class Segment;
46 class Local;
47
48 Worklist() = default;
49 ~Worklist() { CHECK(IsEmpty())do { if ((__builtin_expect(!!(!(IsEmpty())), 0))) { V8_Fatal(
"Check failed: %s.", "IsEmpty()"); } } while (false); }
50
51 void Push(Segment* segment);
52 bool Pop(Segment** segment);
53
54 // Returns true if the list of segments is empty.
55 bool IsEmpty() const;
56 // Returns the number of segments in the list.
57 size_t Size() const;
58
59 // Moves the segments of the given marking worklist into this
60 // marking worklist.
61 void Merge(Worklist<EntryType, SegmentSize>* other);
62
63 // Swaps the segments with the given marking worklist.
64 void Swap(Worklist<EntryType, SegmentSize>* other);
65
66 // These functions are not thread-safe. They should be called only
67 // if all local marking worklists that use the current worklist have
68 // been published and are empty.
69 void Clear();
70 template <typename Callback>
71 void Update(Callback callback);
72 template <typename Callback>
73 void Iterate(Callback callback);
74
75 private:
76 void set_top(Segment* segment) {
77 v8::base::AsAtomicPtr(&top_)->store(segment, std::memory_order_relaxed);
78 }
79
80 v8::base::Mutex lock_;
81 Segment* top_ = nullptr;
82 std::atomic<size_t> size_{0};
83};
84
85template <typename EntryType, uint16_t SegmentSize>
86void Worklist<EntryType, SegmentSize>::Push(Segment* segment) {
87 DCHECK(!segment->IsEmpty())((void) 0);
88 v8::base::MutexGuard guard(&lock_);
89 segment->set_next(top_);
90 set_top(segment);
91 size_.fetch_add(1, std::memory_order_relaxed);
92}
93
94template <typename EntryType, uint16_t SegmentSize>
95bool Worklist<EntryType, SegmentSize>::Pop(Segment** segment) {
96 v8::base::MutexGuard guard(&lock_);
97 if (top_ == nullptr) return false;
98 DCHECK_LT(0U, size_)((void) 0);
99 size_.fetch_sub(1, std::memory_order_relaxed);
100 *segment = top_;
101 set_top(top_->next());
102 return true;
103}
104
105template <typename EntryType, uint16_t SegmentSize>
106bool Worklist<EntryType, SegmentSize>::IsEmpty() const {
107 return v8::base::AsAtomicPtr(&top_)->load(std::memory_order_relaxed) ==
108 nullptr;
109}
110
111template <typename EntryType, uint16_t SegmentSize>
112size_t Worklist<EntryType, SegmentSize>::Size() const {
113 // It is safe to read |size_| without a lock since this variable is
114 // atomic, keeping in mind that threads may not immediately see the new
115 // value when it is updated.
116 return size_.load(std::memory_order_relaxed);
117}
118
119template <typename EntryType, uint16_t SegmentSize>
120void Worklist<EntryType, SegmentSize>::Clear() {
121 v8::base::MutexGuard guard(&lock_);
122 size_.store(0, std::memory_order_relaxed);
123 Segment* current = top_;
124 while (current != nullptr) {
125 Segment* tmp = current;
126 current = current->next();
127 delete tmp;
128 }
129 set_top(nullptr);
130}
131
132template <typename EntryType, uint16_t SegmentSize>
133template <typename Callback>
134void Worklist<EntryType, SegmentSize>::Update(Callback callback) {
135 v8::base::MutexGuard guard(&lock_);
136 Segment* prev = nullptr;
137 Segment* current = top_;
138 size_t num_deleted = 0;
139 while (current != nullptr) {
140 current->Update(callback);
141 if (current->IsEmpty()) {
142 DCHECK_LT(0U, size_)((void) 0);
143 ++num_deleted;
144 if (prev == nullptr) {
145 top_ = current->next();
146 } else {
147 prev->set_next(current->next());
148 }
149 Segment* tmp = current;
150 current = current->next();
151 delete tmp;
152 } else {
153 prev = current;
154 current = current->next();
155 }
156 }
157 size_.fetch_sub(num_deleted, std::memory_order_relaxed);
158}
159
160template <typename EntryType, uint16_t SegmentSize>
161template <typename Callback>
162void Worklist<EntryType, SegmentSize>::Iterate(Callback callback) {
163 v8::base::MutexGuard guard(&lock_);
164 for (Segment* current = top_; current != nullptr; current = current->next()) {
165 current->Iterate(callback);
166 }
167}
168
169template <typename EntryType, uint16_t SegmentSize>
170void Worklist<EntryType, SegmentSize>::Merge(
171 Worklist<EntryType, SegmentSize>* other) {
172 Segment* top = nullptr;
173 size_t other_size = 0;
174 {
175 v8::base::MutexGuard guard(&other->lock_);
176 if (!other->top_) return;
177 top = other->top_;
178 other_size = other->size_.load(std::memory_order_relaxed);
179 other->size_.store(0, std::memory_order_relaxed);
180 other->set_top(nullptr);
181 }
182
183 // It's safe to iterate through these segments because the top was
184 // extracted from |other|.
185 Segment* end = top;
186 while (end->next()) end = end->next();
187
188 {
189 v8::base::MutexGuard guard(&lock_);
190 size_.fetch_add(other_size, std::memory_order_relaxed);
191 end->set_next(top_);
192 set_top(top);
193 }
194}
195
196template <typename EntryType, uint16_t SegmentSize>
197void Worklist<EntryType, SegmentSize>::Swap(
198 Worklist<EntryType, SegmentSize>* other) {
199 Segment* top = top_;
200 set_top(other->top_);
201 other->set_top(top);
202 size_t other_size = other->size_.exchange(
203 size_.load(std::memory_order_relaxed), std::memory_order_relaxed);
204 size_.store(other_size, std::memory_order_relaxed);
205}
206
207template <typename EntryType, uint16_t SegmentSize>
208class Worklist<EntryType, SegmentSize>::Segment : public internal::SegmentBase {
209 public:
210 static const uint16_t kSize = SegmentSize;
211
212 void Push(EntryType entry);
213 void Pop(EntryType* entry);
214
215 template <typename Callback>
216 void Update(Callback callback);
217 template <typename Callback>
218 void Iterate(Callback callback) const;
219
220 Segment* next() const { return next_; }
221 void set_next(Segment* segment) { next_ = segment; }
222
223 private:
224 Segment() : internal::SegmentBase(kSize) {}
225
226 Segment* next_ = nullptr;
227 EntryType entries_[kSize];
228
229 friend class Worklist<EntryType, SegmentSize>::Local;
230
231 FRIEND_TEST(WorkListTest, SegmentCreate)friend class WorkListTest_SegmentCreate_Test;
232 FRIEND_TEST(WorkListTest, SegmentPush)friend class WorkListTest_SegmentPush_Test;
233 FRIEND_TEST(WorkListTest, SegmentPushPop)friend class WorkListTest_SegmentPushPop_Test;
234 FRIEND_TEST(WorkListTest, SegmentIsEmpty)friend class WorkListTest_SegmentIsEmpty_Test;
235 FRIEND_TEST(WorkListTest, SegmentIsFull)friend class WorkListTest_SegmentIsFull_Test;
236 FRIEND_TEST(WorkListTest, SegmentClear)friend class WorkListTest_SegmentClear_Test;
237 FRIEND_TEST(WorkListTest, SegmentUpdateFalse)friend class WorkListTest_SegmentUpdateFalse_Test;
238 FRIEND_TEST(WorkListTest, SegmentUpdate)friend class WorkListTest_SegmentUpdate_Test;
239};
240
241template <typename EntryType, uint16_t SegmentSize>
242void Worklist<EntryType, SegmentSize>::Segment::Push(EntryType entry) {
243 DCHECK(!IsFull())((void) 0);
244 entries_[index_++] = entry;
245}
246
247template <typename EntryType, uint16_t SegmentSize>
248void Worklist<EntryType, SegmentSize>::Segment::Pop(EntryType* entry) {
249 DCHECK(!IsEmpty())((void) 0);
250 *entry = entries_[--index_];
251}
252
253template <typename EntryType, uint16_t SegmentSize>
254template <typename Callback>
255void Worklist<EntryType, SegmentSize>::Segment::Update(Callback callback) {
256 size_t new_index = 0;
257 for (size_t i = 0; i < index_; i++) {
258 if (callback(entries_[i], &entries_[new_index])) {
259 new_index++;
260 }
261 }
262 index_ = new_index;
263}
264
265template <typename EntryType, uint16_t SegmentSize>
266template <typename Callback>
267void Worklist<EntryType, SegmentSize>::Segment::Iterate(
268 Callback callback) const {
269 for (size_t i = 0; i < index_; i++) {
270 callback(entries_[i]);
271 }
272}
273
274// A thread-local view of the marking worklist.
275template <typename EntryType, uint16_t SegmentSize>
276class Worklist<EntryType, SegmentSize>::Local {
277 public:
278 using ItemType = EntryType;
279
280 Local() = default;
281 explicit Local(Worklist<EntryType, SegmentSize>* worklist);
282 ~Local();
283
284 Local(Local&&) V8_NOEXCEPTnoexcept;
285 Local& operator=(Local&&) V8_NOEXCEPTnoexcept;
286
287 // Disable copying since having multiple copies of the same
288 // local marking worklist is unsafe.
289 Local(const Local&) = delete;
290 Local& operator=(const Local& other) = delete;
291
292 void Push(EntryType entry);
293 bool Pop(EntryType* entry);
294
295 bool IsLocalAndGlobalEmpty() const;
296 bool IsLocalEmpty() const;
297 bool IsGlobalEmpty() const;
298
299 void Publish();
300 void Merge(Worklist<EntryType, SegmentSize>::Local* other);
301
302 bool IsEmpty() const;
303 void Clear();
304
305 size_t PushSegmentSize() const { return push_segment_->Size(); }
306
307 private:
308 void PublishPushSegment();
309 void PublishPopSegment();
310 bool StealPopSegment();
311
312 Segment* NewSegment() const {
313 // Bottleneck for filtering in crash dumps.
314 return new Segment();
315 }
316 void DeleteSegment(internal::SegmentBase* segment) const {
317 if (segment == internal::SegmentBase::GetSentinelSegmentAddress()) return;
318 delete static_cast<Segment*>(segment);
319 }
320
321 inline Segment* push_segment() {
322 DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(),((void) 0)
323 push_segment_)((void) 0);
324 return static_cast<Segment*>(push_segment_);
325 }
326 inline const Segment* push_segment() const {
327 DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(),((void) 0)
328 push_segment_)((void) 0);
329 return static_cast<const Segment*>(push_segment_);
330 }
331
332 inline Segment* pop_segment() {
333 DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(), pop_segment_)((void) 0);
334 return static_cast<Segment*>(pop_segment_);
335 }
336 inline const Segment* pop_segment() const {
337 DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(), pop_segment_)((void) 0);
338 return static_cast<const Segment*>(pop_segment_);
339 }
340
341 Worklist<EntryType, SegmentSize>* worklist_ = nullptr;
342 internal::SegmentBase* push_segment_ = nullptr;
343 internal::SegmentBase* pop_segment_ = nullptr;
344};
345
346template <typename EntryType, uint16_t SegmentSize>
347Worklist<EntryType, SegmentSize>::Local::Local(
348 Worklist<EntryType, SegmentSize>* worklist)
349 : worklist_(worklist),
350 push_segment_(internal::SegmentBase::GetSentinelSegmentAddress()),
351 pop_segment_(internal::SegmentBase::GetSentinelSegmentAddress()) {}
352
353template <typename EntryType, uint16_t SegmentSize>
354Worklist<EntryType, SegmentSize>::Local::~Local() {
355 CHECK_IMPLIES(push_segment_, push_segment_->IsEmpty())do { if ((__builtin_expect(!!(!(!(push_segment_) || (push_segment_
->IsEmpty()))), 0))) { V8_Fatal("Check failed: %s.", "push_segment_"
" implies " "push_segment_->IsEmpty()"); } } while (false
);
356 CHECK_IMPLIES(pop_segment_, pop_segment_->IsEmpty())do { if ((__builtin_expect(!!(!(!(pop_segment_) || (pop_segment_
->IsEmpty()))), 0))) { V8_Fatal("Check failed: %s.", "pop_segment_"
" implies " "pop_segment_->IsEmpty()"); } } while (false);
357 DeleteSegment(push_segment_);
358 DeleteSegment(pop_segment_);
359}
360
361template <typename EntryType, uint16_t SegmentSize>
362Worklist<EntryType, SegmentSize>::Local::Local(
363 Worklist<EntryType, SegmentSize>::Local&& other) V8_NOEXCEPTnoexcept {
364 worklist_ = other.worklist_;
365 push_segment_ = other.push_segment_;
366 pop_segment_ = other.pop_segment_;
367 other.worklist_ = nullptr;
368 other.push_segment_ = nullptr;
369 other.pop_segment_ = nullptr;
370}
371
372template <typename EntryType, uint16_t SegmentSize>
373typename Worklist<EntryType, SegmentSize>::Local&
374Worklist<EntryType, SegmentSize>::Local::operator=(
375 Worklist<EntryType, SegmentSize>::Local&& other) V8_NOEXCEPTnoexcept {
376 if (this != &other) {
5
←
Assuming the condition is true
→
6
←
Taking true branch
→
377 DCHECK_NULL(worklist_)((void) 0);
378 DCHECK_NULL(push_segment_)((void) 0);
379 DCHECK_NULL(pop_segment_)((void) 0);
380 worklist_ = other.worklist_;
381 push_segment_ = other.push_segment_;
382 pop_segment_ = other.pop_segment_;
383 other.worklist_ = nullptr;
384 other.push_segment_ = nullptr;
385 other.pop_segment_ = nullptr;
7
←
Null pointer value stored to field 'pop_segment_'
→
386 }
387 return *this;
388}
389
390template <typename EntryType, uint16_t SegmentSize>
391void Worklist<EntryType, SegmentSize>::Local::Push(EntryType entry) {
392 if (V8_UNLIKELY(push_segment_->IsFull())(__builtin_expect(!!(push_segment_->IsFull()), 0))) {
393 PublishPushSegment();
394 }
395 push_segment()->Push(entry);
396}
397
398template <typename EntryType, uint16_t SegmentSize>
399bool Worklist<EntryType, SegmentSize>::Local::Pop(EntryType* entry) {
400 if (pop_segment_->IsEmpty()) {
11
←
Called C++ object pointer is null
401 if (!push_segment_->IsEmpty()) {
402 std::swap(push_segment_, pop_segment_);
403 } else if (!StealPopSegment()) {
404 return false;
405 }
406 }
407 pop_segment()->Pop(entry);
408 return true;
409}
410
411template <typename EntryType, uint16_t SegmentSize>
412bool Worklist<EntryType, SegmentSize>::Local::IsLocalAndGlobalEmpty() const {
413 return IsLocalEmpty() && IsGlobalEmpty();
414}
415
416template <typename EntryType, uint16_t SegmentSize>
417bool Worklist<EntryType, SegmentSize>::Local::IsLocalEmpty() const {
418 return push_segment_->IsEmpty() && pop_segment_->IsEmpty();
419}
420
421template <typename EntryType, uint16_t SegmentSize>
422bool Worklist<EntryType, SegmentSize>::Local::IsGlobalEmpty() const {
423 return worklist_->IsEmpty();
424}
425
426template <typename EntryType, uint16_t SegmentSize>
427void Worklist<EntryType, SegmentSize>::Local::Publish() {
428 if (!push_segment_->IsEmpty()) PublishPushSegment();
429 if (!pop_segment_->IsEmpty()) PublishPopSegment();
430}
431
432template <typename EntryType, uint16_t SegmentSize>
433void Worklist<EntryType, SegmentSize>::Local::Merge(
434 Worklist<EntryType, SegmentSize>::Local* other) {
435 other->Publish();
436 worklist_->Merge(other->worklist_);
437}
438
439template <typename EntryType, uint16_t SegmentSize>
440void Worklist<EntryType, SegmentSize>::Local::PublishPushSegment() {
441 if (push_segment_ != internal::SegmentBase::GetSentinelSegmentAddress())
442 worklist_->Push(push_segment());
443 push_segment_ = NewSegment();
444}
445
446template <typename EntryType, uint16_t SegmentSize>
447void Worklist<EntryType, SegmentSize>::Local::PublishPopSegment() {
448 if (pop_segment_ != internal::SegmentBase::GetSentinelSegmentAddress())
449 worklist_->Push(pop_segment());
450 pop_segment_ = NewSegment();
451}
452
453template <typename EntryType, uint16_t SegmentSize>
454bool Worklist<EntryType, SegmentSize>::Local::StealPopSegment() {
455 if (worklist_->IsEmpty()) return false;
456 Segment* new_segment = nullptr;
457 if (worklist_->Pop(&new_segment)) {
458 DeleteSegment(pop_segment_);
459 pop_segment_ = new_segment;
460 return true;
461 }
462 return false;
463}
464
465template <typename EntryType, uint16_t SegmentSize>
466bool Worklist<EntryType, SegmentSize>::Local::IsEmpty() const {
467 return push_segment_->IsEmpty() && pop_segment_->IsEmpty();
468}
469
470template <typename EntryType, uint16_t SegmentSize>
471void Worklist<EntryType, SegmentSize>::Local::Clear() {
472 push_segment_->Clear();
473 pop_segment_->Clear();
474}
475
476} // namespace base
477} // namespace heap
478
479#endif // V8_HEAP_BASE_WORKLIST_H_