beenull/ladybird
1
0
Fork 0
mirror of https://github.com/LadybirdBrowser/ladybird.git synced 2024-11-21 23:20:20 +00:00
Code Issues Projects Releases Packages Wiki Activity Actions 6
ladybird/Libraries/LibGC/Heap.cpp

539 lines
19 KiB
C++
Raw Permalink Normal View History

LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
/*
Meta: Update my e-mail address everywhere
2024-10-04 11:19:50 +00:00
* Copyright (c) 2020-2022, Andreas Kling <andreas@ladybird.org>
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
* Copyright (c) 2023, Aliaksandr Kalenik <kalenik.aliaksandr@gmail.com>
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
*
Everything: Move to SPDX license identifiers in all files. SPDX License Identifiers are a more compact / standardized way of representing file license information. See: https://spdx.dev/resources/use/#identifiers This was done with the `ambr` search and replace tool. ambr --no-parent-ignore --key-from-file --rep-from-file key.txt rep.txt *
2021-04-22 08:24:48 +00:00
* SPDX-License-Identifier: BSD-2-Clause
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
*/
LibJS: Make sure we mark everything reachable from the scope stack This ensures that local variables survive GC.
2020-03-09 20:29:22 +00:00
#include <AK/Badge.h>
Everywhere: Hook up remaining debug macros to Debug.h.
2021-01-24 14:28:26 +00:00
#include <AK/Debug.h>
LibJS: Use a Function to indirectly let Heap visit VM's GC roots This allows the heap to mark cells that it needs to mark as roots without needing to directly reference the VM.
2024-11-14 07:17:33 +00:00
#include <AK/Function.h>
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
#include <AK/HashTable.h>
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
#include <AK/JsonArray.h>
#include <AK/JsonObject.h>
LibJS: Use toolchain agnostic NO_SANITIZE_ADDRESS
2024-04-08 00:28:28 +00:00
#include <AK/Platform.h>
LibJS+AK: Move cross-platform stack bounds code from JS::Heap to AK::StackInfo This will be useful for other things than the Heap, maybe even outside of LibJS.
2020-11-08 12:48:16 +00:00
#include <AK/StackInfo.h>
Everywhere: Add missing <AK/TemporaryChange.h> includes Don't rely on HashTable.h pulling this in.
2020-10-15 18:46:52 +00:00
#include <AK/TemporaryChange.h>
LibJS: Add API for doing GC with a little debug log report at end You can now pass print_report=true to Heap::collect_garbage() and it will print out a little summary of the time spent, and counts of live vs freed cells and blocks.
2020-08-16 18:33:56 +00:00
#include <LibCore/ElapsedTimer.h>
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
#include <LibGC/CellAllocator.h>
#include <LibGC/Heap.h>
#include <LibGC/HeapBlock.h>
#include <LibGC/NanBoxedValue.h>
#include <LibGC/Root.h>
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
#include <setjmp.h>
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
LibJS: Check the ASAN fake stack for heap pointers when ASAN is enabled This is a similar strategy to what v8 does. Use the ASAN API function __asan_addr_is_in_fake_stack to check any fake stack frames associated with each stack address we scan. This fully allows running test-js -g with the option detect_stack_use_after_return turned on.
2023-07-01 00:46:12 +00:00
#ifdef HAS_ADDRESS_SANITIZER
# include <sanitizer/asan_interface.h>
#endif
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
namespace GC {
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
Heap::Heap(void* private_data, AK::Function<void(HashMap<Cell*, GC::HeapRoot>&)> gather_embedder_roots)
LibJS: Don't directly teach the heap about the javascript VM or Realm Instead, smuggle it in as a `void*` private data and let Javascript aware code cast out that pointer to a VM&. In order to make this split, rename JS::Cell to JS::CellImpl. Once we have a LibGC, this will become GC::Cell. CellImpl then has no specific knowledge of the VM& and Realm&. That knowledge is instead put into JS::Cell, which inherits from CellImpl. JS::Cell is responsible for JavaScript's realm initialization, as well as converting of the void* private data to what it knows should be the VM&.
2024-11-14 07:22:33 +00:00
: HeapBase(private_data)
LibJS: Use a Function to indirectly let Heap visit VM's GC roots This allows the heap to mark cells that it needs to mark as roots without needing to directly reference the VM.
2024-11-14 07:17:33 +00:00
, m_gather_embedder_roots(move(gather_embedder_roots))
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
{
LibJS: Make JS::Cell a Weakable This makes things easier downstream of Cell, and is preparation for using weak pointers in prototype chain property caches.
2024-05-02 08:24:23 +00:00
static_assert(HeapBlock::min_possible_cell_size <= 32, "Heap Cell tracking uses too much data!");
LibJS: Make Heap aware of all CellAllocators Also add a link from HeapBlock to their owning CellAllocator. This fixes an issue where the Heap would skip over non-size-based cell allocators.
2023-12-23 14:13:51 +00:00
m_size_based_cell_allocators.append(make<CellAllocator>(64));
m_size_based_cell_allocators.append(make<CellAllocator>(96));
m_size_based_cell_allocators.append(make<CellAllocator>(128));
m_size_based_cell_allocators.append(make<CellAllocator>(256));
m_size_based_cell_allocators.append(make<CellAllocator>(512));
m_size_based_cell_allocators.append(make<CellAllocator>(1024));
m_size_based_cell_allocators.append(make<CellAllocator>(3072));
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
}
Heap::~Heap()
{
LibJS: Always collect all garbage when destroying Heap When the Heap is going down, it's our last chance to run destructors, so add a separate collector mode where we simply skip over the marking phase and go directly to sweeping. This causes everything to get swept and all live cells get destroyed. This way, valgrind reports 0 leaks on exit. :^)
2020-03-23 13:11:19 +00:00
collect_garbage(CollectionType::CollectEverything);
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
}
LibJS: Segregate GC-allocated objects by type This patch adds two macros to declare per-type allocators: - JS_DECLARE_ALLOCATOR(TypeName) - JS_DEFINE_ALLOCATOR(TypeName) When used, they add a type-specific CellAllocator that the Heap will delegate allocation requests to. The result of this is that GC objects of the same type always end up within the same HeapBlock, drastically reducing the ability to perform type confusion attacks. It also improves HeapBlock utilization, since each block now has cells sized exactly to the type used within that block. (Previously we only had a handful of block sizes available, and most GC allocations ended up with a large amount of slack in their tails.) There is a small performance hit from this, but I'm sure we can make up for it elsewhere. Note that the old size-based allocators still exist, and we fall back to them for any type that doesn't have its own CellAllocator.
2023-11-19 08:45:05 +00:00
void Heap::will_allocate(size_t size)
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
{
LibJS: Do a garbage collection every N allocations (N=10'000) To prevent the heap from growing infinitely large, we now do a full GC every 10'000 allocations. :^)
2020-04-06 10:36:49 +00:00
if (should_collect_on_every_allocation()) {
LibJS: Improve garbage collection trigger condition This patch triggers the collector when allocated memory doubles instead of every 100k allocations. Which can almost half (reduce by ~48%) the time spent on collection when loading google-maps. This dynamic approach is inspired by some other GCs like Golang's and Lua's and improves performance in memory heavy applications because marking must visit old objects which will dominate the marking phase if the GC is invoked too often. This commit also improves the Octane Splay benchmark and almost doubles it :^)
2023-08-08 17:50:32 +00:00
m_allocated_bytes_since_last_gc = 0;
LibJS+js: Add a debug option (js -g) to GC after every allocation This is very useful for discovering collector bugs.
2020-03-16 18:18:46 +00:00
collect_garbage();
LibJS: Improve garbage collection trigger condition This patch triggers the collector when allocated memory doubles instead of every 100k allocations. Which can almost half (reduce by ~48%) the time spent on collection when loading google-maps. This dynamic approach is inspired by some other GCs like Golang's and Lua's and improves performance in memory heavy applications because marking must visit old objects which will dominate the marking phase if the GC is invoked too often. This commit also improves the Octane Splay benchmark and almost doubles it :^)
2023-08-08 17:50:32 +00:00
} else if (m_allocated_bytes_since_last_gc + size > m_gc_bytes_threshold) {
m_allocated_bytes_since_last_gc = 0;
LibJS: Do a garbage collection every N allocations (N=10'000) To prevent the heap from growing infinitely large, we now do a full GC every 10'000 allocations. :^)
2020-04-06 10:36:49 +00:00
collect_garbage();
}
LibJS+js: Add a debug option (js -g) to GC after every allocation This is very useful for discovering collector bugs.
2020-03-16 18:18:46 +00:00
LibJS: Improve garbage collection trigger condition This patch triggers the collector when allocated memory doubles instead of every 100k allocations. Which can almost half (reduce by ~48%) the time spent on collection when loading google-maps. This dynamic approach is inspired by some other GCs like Golang's and Lua's and improves performance in memory heavy applications because marking must visit old objects which will dominate the marking phase if the GC is invoked too often. This commit also improves the Octane Splay benchmark and almost doubles it :^)
2023-08-08 17:50:32 +00:00
m_allocated_bytes_since_last_gc += size;
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
}
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
static void add_possible_value(HashMap<FlatPtr, HeapRoot>& possible_pointers, FlatPtr data, HeapRoot origin, FlatPtr min_block_address, FlatPtr max_block_address)
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
{
LibJS: Make Value inherit from a NanBoxedValue NanBoxedValue is intended to be a GC-allocatable type which is not specific to javascript, towards the effort of factoring out the GC implementation from LibJS.
2024-11-14 06:40:36 +00:00
if constexpr (sizeof(FlatPtr*) == sizeof(NanBoxedValue)) {
// Because NanBoxedValue stores pointers in non-canonical form we have to check if the top bytes
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
// match any pointer-backed tag, in that case we have to extract the pointer to its
// canonical form and add that as a possible pointer.
LibJS: Fix two bugs in the GC fast rejection of possible pointers - Convert to FlatPtr instead of doing pointer arithmetic on a too-large pointer type in find_min_and_max_block_addresses(). This makes the range more accurate. - Untag possible cell pointers in add_possible_value() before doing the rejection. Otherwise we end up rejecting most pointers since the tags sit in the highest bits! This fixes a crash when running the Speedometer benchmark.
2023-09-30 07:48:01 +00:00
FlatPtr possible_pointer;
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
if ((data & SHIFTED_IS_CELL_PATTERN) == SHIFTED_IS_CELL_PATTERN)
LibJS: Make Value inherit from a NanBoxedValue NanBoxedValue is intended to be a GC-allocatable type which is not specific to javascript, towards the effort of factoring out the GC implementation from LibJS.
2024-11-14 06:40:36 +00:00
possible_pointer = NanBoxedValue::extract_pointer_bits(data);
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
else
LibJS: Fix two bugs in the GC fast rejection of possible pointers - Convert to FlatPtr instead of doing pointer arithmetic on a too-large pointer type in find_min_and_max_block_addresses(). This makes the range more accurate. - Untag possible cell pointers in add_possible_value() before doing the rejection. Otherwise we end up rejecting most pointers since the tags sit in the highest bits! This fixes a crash when running the Speedometer benchmark.
2023-09-30 07:48:01 +00:00
possible_pointer = data;
if (possible_pointer < min_block_address || possible_pointer > max_block_address)
return;
possible_pointers.set(possible_pointer, move(origin));
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
} else {
LibJS: Make Value inherit from a NanBoxedValue NanBoxedValue is intended to be a GC-allocatable type which is not specific to javascript, towards the effort of factoring out the GC implementation from LibJS.
2024-11-14 06:40:36 +00:00
static_assert((sizeof(NanBoxedValue) % sizeof(FlatPtr*)) == 0);
LibJS: Fix two bugs in the GC fast rejection of possible pointers - Convert to FlatPtr instead of doing pointer arithmetic on a too-large pointer type in find_min_and_max_block_addresses(). This makes the range more accurate. - Untag possible cell pointers in add_possible_value() before doing the rejection. Otherwise we end up rejecting most pointers since the tags sit in the highest bits! This fixes a crash when running the Speedometer benchmark.
2023-09-30 07:48:01 +00:00
if (data < min_block_address || data > max_block_address)
return;
LibJS: Make Value inherit from a NanBoxedValue NanBoxedValue is intended to be a GC-allocatable type which is not specific to javascript, towards the effort of factoring out the GC implementation from LibJS.
2024-11-14 06:40:36 +00:00
// In the 32-bit case we will look at the top and bottom part of NanBoxedValue separately we just
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
// add both the upper and lower bytes as possible pointers.
possible_pointers.set(data, move(origin));
}
}
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
void Heap::find_min_and_max_block_addresses(FlatPtr& min_address, FlatPtr& max_address)
{
LibJS: Fix two bugs in the GC fast rejection of possible pointers - Convert to FlatPtr instead of doing pointer arithmetic on a too-large pointer type in find_min_and_max_block_addresses(). This makes the range more accurate. - Untag possible cell pointers in add_possible_value() before doing the rejection. Otherwise we end up rejecting most pointers since the tags sit in the highest bits! This fixes a crash when running the Speedometer benchmark.
2023-09-30 07:48:01 +00:00
min_address = explode_byte(0xff);
max_address = 0;
LibJS: Save min and max block addresses in CellAllocator This allows to skip iterating through all allocated blocks in `find_min_and_max_block_addresses()`. With this change `collect_garbage()` in profiles of Discord goes down from 17% to 8%.
2024-04-23 14:53:59 +00:00
for (auto& allocator : m_all_cell_allocators) {
min_address = min(min_address, allocator.min_block_address());
max_address = max(max_address, allocator.max_block_address() + HeapBlockBase::block_size);
}
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
}
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
template<typename Callback>
LibJS: Add source location for Handle nodes in GC graph dumper output With this change JS::Handle root nodes will contain source location where they were constructed like: ``` "94675029575744": { "root": "Handle activate_event_handler \ serenity/Userland/Libraries/LibWeb/DOM/EventTarget.cpp:564", "class_name": "HTMLButtonElement", "edges": [ "94675025955904", "94675026899520", "94675030831168", ```
2023-09-22 00:04:16 +00:00
static void for_each_cell_among_possible_pointers(HashTable<HeapBlock*> const& all_live_heap_blocks, HashMap<FlatPtr, HeapRoot>& possible_pointers, Callback callback)
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
{
for (auto possible_pointer : possible_pointers.keys()) {
if (!possible_pointer)
continue;
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
auto* possible_heap_block = HeapBlock::from_cell(reinterpret_cast<Cell const*>(possible_pointer));
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
if (!all_live_heap_blocks.contains(possible_heap_block))
continue;
if (auto* cell = possible_heap_block->cell_from_possible_pointer(possible_pointer)) {
callback(cell, possible_pointer);
}
}
}
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
class GraphConstructorVisitor final : public Cell::Visitor {
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
public:
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
explicit GraphConstructorVisitor(Heap& heap, HashMap<Cell*, HeapRoot> const& roots)
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
: m_heap(heap)
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
{
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
m_heap.find_min_and_max_block_addresses(m_min_block_address, m_max_block_address);
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
m_heap.for_each_block([&](auto& block) {
m_all_live_heap_blocks.set(&block);
return IterationDecision::Continue;
});
LibJS: Simplify iteration in GC heap dumping code
2024-04-20 16:41:11 +00:00
for (auto& [root, root_origin] : roots) {
auto& graph_node = m_graph.ensure(bit_cast<FlatPtr>(root));
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
graph_node.class_name = root->class_name();
LibJS: Simplify iteration in GC heap dumping code
2024-04-20 16:41:11 +00:00
graph_node.root_origin = root_origin;
m_work_queue.append(*root);
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
}
}
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
virtual void visit_impl(Cell& cell) override
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
{
if (m_node_being_visited)
m_node_being_visited->edges.set(reinterpret_cast<FlatPtr>(&cell));
if (m_graph.get(reinterpret_cast<FlatPtr>(&cell)).has_value())
return;
m_work_queue.append(cell);
}
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
virtual void visit_possible_values(ReadonlyBytes bytes) override
{
LibJS: Add source location for Handle nodes in GC graph dumper output With this change JS::Handle root nodes will contain source location where they were constructed like: ``` "94675029575744": { "root": "Handle activate_event_handler \ serenity/Userland/Libraries/LibWeb/DOM/EventTarget.cpp:564", "class_name": "HTMLButtonElement", "edges": [ "94675025955904", "94675026899520", "94675030831168", ```
2023-09-22 00:04:16 +00:00
HashMap<FlatPtr, HeapRoot> possible_pointers;
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
auto* raw_pointer_sized_values = reinterpret_cast<FlatPtr const*>(bytes.data());
for (size_t i = 0; i < (bytes.size() / sizeof(FlatPtr)); ++i)
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
add_possible_value(possible_pointers, raw_pointer_sized_values[i], HeapRoot { .type = HeapRoot::Type::HeapFunctionCapturedPointer }, m_min_block_address, m_max_block_address);
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
for_each_cell_among_possible_pointers(m_all_live_heap_blocks, possible_pointers, [&](Cell* cell, FlatPtr) {
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
if (m_node_being_visited)
LibJS: Use correct cell address for HeapFunction captures in GC dumps We were previously dumping the address of the cell pointer instead of the address of the cell itself. This was causing mysterious orphans in GC dumps, and it took me way too long to figure this out.
2024-11-11 14:45:51 +00:00
m_node_being_visited->edges.set(reinterpret_cast<FlatPtr>(cell));
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
if (m_graph.get(reinterpret_cast<FlatPtr>(&cell)).has_value())
return;
m_work_queue.append(*cell);
});
}
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
void visit_all_cells()
{
while (!m_work_queue.is_empty()) {
LibJS: Simplify iteration in GC heap dumping code
2024-04-20 16:41:11 +00:00
auto cell = m_work_queue.take_last();
m_node_being_visited = &m_graph.ensure(bit_cast<FlatPtr>(cell.ptr()));
m_node_being_visited->class_name = cell->class_name();
cell->visit_edges(*this);
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
m_node_being_visited = nullptr;
}
}
LibJS+LibWebView+WebContent+Ladybird: Output GC-graph into a file Instead of displaying a massive JSON in stdout, it's more practical to save the GC-graph to a file.
2023-12-12 12:25:06 +00:00
AK::JsonObject dump()
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
{
auto graph = AK::JsonObject();
for (auto& it : m_graph) {
AK::JsonArray edges;
for (auto const& value : it.value.edges) {
Everywhere: Rename {Deprecated => Byte}String This commit un-deprecates DeprecatedString, and repurposes it as a byte string. As the null state has already been removed, there are no other particularly hairy blockers in repurposing this type as a byte string (what it _really_ is). This commit is auto-generated: $ xs=$(ack -l \bDeprecatedString\b\|deprecated_string AK Userland \ Meta Ports Ladybird Tests Kernel) $ perl -pie 's/\bDeprecatedString\b/ByteString/g; s/deprecated_string/byte_string/g' $xs $ clang-format --style=file -i \ $(git diff --name-only | grep \.cpp\|\.h) $ gn format $(git ls-files '*.gn' '*.gni')
2023-12-16 14:19:34 +00:00
edges.must_append(ByteString::formatted("{}", value));
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
}
auto node = AK::JsonObject();
if (it.value.root_origin.has_value()) {
LibJS: Add source location for Handle nodes in GC graph dumper output With this change JS::Handle root nodes will contain source location where they were constructed like: ``` "94675029575744": { "root": "Handle activate_event_handler \ serenity/Userland/Libraries/LibWeb/DOM/EventTarget.cpp:564", "class_name": "HTMLButtonElement", "edges": [ "94675025955904", "94675026899520", "94675030831168", ```
2023-09-22 00:04:16 +00:00
auto type = it.value.root_origin->type;
auto location = it.value.root_origin->location;
switch (type) {
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
case HeapRoot::Type::Root:
node.set("root"sv, ByteString::formatted("Root {} {}:{}", location->function_name(), location->filename(), location->line_number()));
LibJS: Add source location for Handle nodes in GC graph dumper output With this change JS::Handle root nodes will contain source location where they were constructed like: ``` "94675029575744": { "root": "Handle activate_event_handler \ serenity/Userland/Libraries/LibWeb/DOM/EventTarget.cpp:564", "class_name": "HTMLButtonElement", "edges": [ "94675025955904", "94675026899520", "94675030831168", ```
2023-09-22 00:04:16 +00:00
break;
case HeapRoot::Type::MarkedVector:
node.set("root"sv, "MarkedVector");
break;
case HeapRoot::Type::RegisterPointer:
node.set("root"sv, "RegisterPointer");
break;
case HeapRoot::Type::StackPointer:
node.set("root"sv, "StackPointer");
break;
case HeapRoot::Type::VM:
node.set("root"sv, "VM");
break;
default:
VERIFY_NOT_REACHED();
}
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
}
node.set("class_name"sv, it.value.class_name);
node.set("edges"sv, edges);
Everywhere: Rename {Deprecated => Byte}String This commit un-deprecates DeprecatedString, and repurposes it as a byte string. As the null state has already been removed, there are no other particularly hairy blockers in repurposing this type as a byte string (what it _really_ is). This commit is auto-generated: $ xs=$(ack -l \bDeprecatedString\b\|deprecated_string AK Userland \ Meta Ports Ladybird Tests Kernel) $ perl -pie 's/\bDeprecatedString\b/ByteString/g; s/deprecated_string/byte_string/g' $xs $ clang-format --style=file -i \ $(git diff --name-only | grep \.cpp\|\.h) $ gn format $(git ls-files '*.gn' '*.gni')
2023-12-16 14:19:34 +00:00
graph.set(ByteString::number(it.key), node);
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
}
LibJS+LibWebView+WebContent+Ladybird: Output GC-graph into a file Instead of displaying a massive JSON in stdout, it's more practical to save the GC-graph to a file.
2023-12-12 12:25:06 +00:00
return graph;
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
}
private:
struct GraphNode {
LibJS: Add source location for Handle nodes in GC graph dumper output With this change JS::Handle root nodes will contain source location where they were constructed like: ``` "94675029575744": { "root": "Handle activate_event_handler \ serenity/Userland/Libraries/LibWeb/DOM/EventTarget.cpp:564", "class_name": "HTMLButtonElement", "edges": [ "94675025955904", "94675026899520", "94675030831168", ```
2023-09-22 00:04:16 +00:00
Optional<HeapRoot> root_origin;
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
StringView class_name;
HashTable<FlatPtr> edges {};
};
GraphNode* m_node_being_visited { nullptr };
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
Vector<Ref<Cell>> m_work_queue;
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
HashMap<FlatPtr, GraphNode> m_graph;
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
Heap& m_heap;
HashTable<HeapBlock*> m_all_live_heap_blocks;
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
FlatPtr m_min_block_address;
FlatPtr m_max_block_address;
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
};
LibJS+LibWebView+WebContent+Ladybird: Output GC-graph into a file Instead of displaying a massive JSON in stdout, it's more practical to save the GC-graph to a file.
2023-12-12 12:25:06 +00:00
AK::JsonObject Heap::dump_graph()
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
{
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
HashMap<Cell*, HeapRoot> roots;
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
gather_roots(roots);
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
GraphConstructorVisitor visitor(*this, roots);
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
visitor.visit_all_cells();
LibJS+LibWebView+WebContent+Ladybird: Output GC-graph into a file Instead of displaying a massive JSON in stdout, it's more practical to save the GC-graph to a file.
2023-12-12 12:25:06 +00:00
return visitor.dump();
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
}
LibJS: Add API for doing GC with a little debug log report at end You can now pass print_report=true to Heap::collect_garbage() and it will print out a little summary of the time spent, and counts of live vs freed cells and blocks.
2020-08-16 18:33:56 +00:00
void Heap::collect_garbage(CollectionType collection_type, bool print_report)
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
{
Everywhere: Rename ASSERT => VERIFY (...and ASSERT_NOT_REACHED => VERIFY_NOT_REACHED) Since all of these checks are done in release builds as well, let's rename them to VERIFY to prevent confusion, as everyone is used to assertions being compiled out in release. We can introduce a new ASSERT macro that is specifically for debug checks, but I'm doing this wholesale conversion first since we've accumulated thousands of these already, and it's not immediately obvious which ones are suitable for ASSERT.
2021-02-23 19:42:32 +00:00
VERIFY(!m_collecting_garbage);
LibJS: Assert if garbage collection is restarted while ongoing We can't GC while we're already in GC. Assert if this happens.
2020-09-21 12:35:19 +00:00
TemporaryChange change(m_collecting_garbage, true);
LibJS: Only start ElapsedTimer for GC metrics when printing is enabled We don't need to be checking the current time unconditionally when we only observe the results if we're going to dump the GC stats. This saves two trips to clock_gettime at the cost of an extra branch.
2023-01-02 05:45:28 +00:00
Core::ElapsedTimer collection_measurement_timer;
if (print_report)
collection_measurement_timer.start();
LibJS: Always collect all garbage when destroying Heap When the Heap is going down, it's our last chance to run destructors, so add a separate collector mode where we simply skip over the marking phase and go directly to sweeping. This causes everything to get swept and all live cells get destroyed. This way, valgrind reports 0 leaks on exit. :^)
2020-03-23 13:11:19 +00:00
if (collection_type == CollectionType::CollectGarbage) {
LibJS: Add DeferGC, a RAII way to prevent GC temporarily
2020-04-19 09:30:47 +00:00
if (m_gc_deferrals) {
m_should_gc_when_deferral_ends = true;
return;
}
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
HashMap<Cell*, HeapRoot> roots;
LibJS: Always collect all garbage when destroying Heap When the Heap is going down, it's our last chance to run destructors, so add a separate collector mode where we simply skip over the marking phase and go directly to sweeping. This causes everything to get swept and all live cells get destroyed. This way, valgrind reports 0 leaks on exit. :^)
2020-03-23 13:11:19 +00:00
gather_roots(roots);
mark_live_cells(roots);
}
LibJS: Add a finalization pass to the garbage collector Doing things in the destructor of a GC-allocated object isn't always safe, in case it involves accessing other GC-allocated objects. If they were already swept by GC, we'd be poking into freed memory. This patch adds a separate finalization pass where GC calls finalize() on every unmarked cell that's about to be deleted. It's safe to access other GC objects in finalize(), even if they're also unmarked.
2022-10-20 16:35:19 +00:00
finalize_unmarked_cells();
LibJS: Add API for doing GC with a little debug log report at end You can now pass print_report=true to Heap::collect_garbage() and it will print out a little summary of the time spent, and counts of live vs freed cells and blocks.
2020-08-16 18:33:56 +00:00
sweep_dead_cells(print_report, collection_measurement_timer);
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
}
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
void Heap::gather_roots(HashMap<Cell*, HeapRoot>& roots)
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
{
LibJS: Use a Function to indirectly let Heap visit VM's GC roots This allows the heap to mark cells that it needs to mark as roots without needing to directly reference the VM.
2024-11-14 07:17:33 +00:00
m_gather_embedder_roots(roots);
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
gather_conservative_roots(roots);
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
for (auto& root : m_roots)
roots.set(root.cell(), HeapRoot { .type = HeapRoot::Type::Root, .location = &root.source_location() });
LibJS: Add Handle<T>, a strong C++ handle for keeping GC objects alive This is pretty heavy and unoptimized, but it will do the trick for now. Basically, Heap now has a HashTable<HandleImpl*> and you can call JS::make_handle(T*) to construct a Handle<T> that guarantees that the pointee will always survive GC until the Handle<T> is destroyed.
2020-03-18 19:03:17 +00:00
LibJS: Let MarkedVector<T> inherit from Vector and handle Cell* + Value Note: MarkedVector is still relatively new and has zero users right now, so these changes don't affect any code other than the class itself. Reasons for this are the rather limited API: - Despite the name and unlike MarkedValueList, MarkedVector isn't actually a Vector, it *wraps* a Vector. This means that plenty of convenient APIs are unavailable and have to be exported on the class separately and forwarded to the internal Vector, or need to go through the exposed Span - both not great options. - Exposing append(Cell*) and prepend(Cell*) on the base class means that it was possible to append any Cell type, not just T! All the strong typing guarantees are basically gone, and MarkedVector doesn't do much more than casting Cells to the appropriate type through the exposed Span. All of this combined means that MarkedVector - in its current form - doesn't provide much value over MarkedValueList, and that we have to maintain two separate, yet almost identical classes. Let's fix this! The updated MarkedVector steals various concepts from the existing MarkedValueList, especially the ability to copy. On the other hand, it remains generic enough to handle both Cell* and Value for T, making MarkedValueList effectively redundant :^) Additionally, by inheriting from Vector we get all the current and future APIs without having to select and expose them separately. MarkedVectorBase remains and takes care of communicating creation and destruction of the class to the heap. Visiting the contained values is handled via a pure virtual method gather_roots(), which is being called by the Heap's function of the same name; much like the VM has one. From there, values are added to the roots HashTable if they are cells for T = Value, and unconditionally for any other T. As a small additional improvement the template now also takes an inline_capacity parameter, defaulting to 32, and forwards it to the Vector template; allowing for possible future optimizations of current uses of MarkedValueList, which hard-codes it to 32.
2022-02-09 09:40:49 +00:00
for (auto& vector : m_marked_vectors)
vector.gather_roots(roots);
LibJS: Add MarkedVector<T> This abstracts a vector of Cell* with a strongly typed span() accessor that gives you Span<T*> instead of Span<Cell*>. It is intended to replace MarkedValueList in situations where you only need to store pointers to Cell (or an even more specific type of Cell). The API can definitely be improved, it's just the bare basics for now.
2021-12-16 17:54:06 +00:00
LibJS: Use 'if constexpr' instead of '#if HEAP_DEBUG'
2021-04-18 16:12:33 +00:00
if constexpr (HEAP_DEBUG) {
dbgln("gather_roots:");
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
for (auto* root : roots.keys())
LibJS: Use 'if constexpr' instead of '#if HEAP_DEBUG'
2021-04-18 16:12:33 +00:00
dbgln(" + {}", root);
}
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
}
LibJS: Check the ASAN fake stack for heap pointers when ASAN is enabled This is a similar strategy to what v8 does. Use the ASAN API function __asan_addr_is_in_fake_stack to check any fake stack frames associated with each stack address we scan. This fully allows running test-js -g with the option detect_stack_use_after_return turned on.
2023-07-01 00:46:12 +00:00
#ifdef HAS_ADDRESS_SANITIZER
LibJS: Use toolchain agnostic NO_SANITIZE_ADDRESS
2024-04-08 00:28:28 +00:00
NO_SANITIZE_ADDRESS void Heap::gather_asan_fake_stack_roots(HashMap<FlatPtr, HeapRoot>& possible_pointers, FlatPtr addr, FlatPtr min_block_address, FlatPtr max_block_address)
LibJS: Check the ASAN fake stack for heap pointers when ASAN is enabled This is a similar strategy to what v8 does. Use the ASAN API function __asan_addr_is_in_fake_stack to check any fake stack frames associated with each stack address we scan. This fully allows running test-js -g with the option detect_stack_use_after_return turned on.
2023-07-01 00:46:12 +00:00
{
void* begin = nullptr;
void* end = nullptr;
void* real_stack = __asan_addr_is_in_fake_stack(__asan_get_current_fake_stack(), reinterpret_cast<void*>(addr), &begin, &end);
if (real_stack != nullptr) {
for (auto* real_stack_addr = reinterpret_cast<void const* const*>(begin); real_stack_addr < end; ++real_stack_addr) {
void const* real_address = *real_stack_addr;
if (real_address == nullptr)
continue;
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
add_possible_value(possible_pointers, reinterpret_cast<FlatPtr>(real_address), HeapRoot { .type = HeapRoot::Type::StackPointer }, min_block_address, max_block_address);
LibJS: Check the ASAN fake stack for heap pointers when ASAN is enabled This is a similar strategy to what v8 does. Use the ASAN API function __asan_addr_is_in_fake_stack to check any fake stack frames associated with each stack address we scan. This fully allows running test-js -g with the option detect_stack_use_after_return turned on.
2023-07-01 00:46:12 +00:00
}
}
}
#else
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
void Heap::gather_asan_fake_stack_roots(HashMap<FlatPtr, HeapRoot>&, FlatPtr, FlatPtr, FlatPtr)
LibJS: Check the ASAN fake stack for heap pointers when ASAN is enabled This is a similar strategy to what v8 does. Use the ASAN API function __asan_addr_is_in_fake_stack to check any fake stack frames associated with each stack address we scan. This fully allows running test-js -g with the option detect_stack_use_after_return turned on.
2023-07-01 00:46:12 +00:00
{
}
#endif
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
NO_SANITIZE_ADDRESS void Heap::gather_conservative_roots(HashMap<Cell*, HeapRoot>& roots)
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
{
FlatPtr dummy;
LibJS: Use dbgln_if in Heap.cpp
2021-04-07 13:12:32 +00:00
dbgln_if(HEAP_DEBUG, "gather_conservative_roots:");
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
jmp_buf buf;
setjmp(buf);
LibJS: Add source location for Handle nodes in GC graph dumper output With this change JS::Handle root nodes will contain source location where they were constructed like: ``` "94675029575744": { "root": "Handle activate_event_handler \ serenity/Userland/Libraries/LibWeb/DOM/EventTarget.cpp:564", "class_name": "HTMLButtonElement", "edges": [ "94675025955904", "94675026899520", "94675030831168", ```
2023-09-22 00:04:16 +00:00
HashMap<FlatPtr, HeapRoot> possible_pointers;
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
LibJS: Fix clang-tidy warnings about redundant types in Heap.cpp
2021-05-25 17:03:30 +00:00
auto* raw_jmp_buf = reinterpret_cast<FlatPtr const*>(buf);
LibJS: Port garbage collector to Linux Well that was easy. LibJS can now run on Linux :^)
2020-03-23 12:14:57 +00:00
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
FlatPtr min_block_address, max_block_address;
find_min_and_max_block_addresses(min_block_address, max_block_address);
LibJS: Don't skip CPU registers when gathering conservative roots We were accidentally skipping over most of the CPU registers by incrementing the register index by sizeof(FlatPtr) instead of 1. This fixes a long-standing issue where live objects could still get garbage-collected if they were only pointed to by an unlucky register.
2023-03-13 19:43:01 +00:00
for (size_t i = 0; i < ((size_t)sizeof(buf)) / sizeof(FlatPtr); ++i)
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
add_possible_value(possible_pointers, raw_jmp_buf[i], HeapRoot { .type = HeapRoot::Type::RegisterPointer }, min_block_address, max_block_address);
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
LibJS: Fix clang-tidy warnings about redundant types in Heap.cpp
2021-05-25 17:03:30 +00:00
auto stack_reference = bit_cast<FlatPtr>(&dummy);
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
LibJS: Make Heap own its own StackInfo instance While this does mean that we keep one copy of the stack info in the VM, and another in the Heap; keeping a separate instance removes one more instance of coupling between the heap and LibJS specific details.
2024-08-18 10:04:55 +00:00
for (FlatPtr stack_address = stack_reference; stack_address < m_stack_info.top(); stack_address += sizeof(FlatPtr)) {
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
auto data = *reinterpret_cast<FlatPtr*>(stack_address);
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
add_possible_value(possible_pointers, data, HeapRoot { .type = HeapRoot::Type::StackPointer }, min_block_address, max_block_address);
gather_asan_fake_stack_roots(possible_pointers, data, min_block_address, max_block_address);
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
}
LibJS: Add ConservativeVector<T> This works very similarly to MarkedVector<T>, but instead of expecting T to be Value or a GC-allocated pointer type, T can be anything. Every pointer-sized value in the vector's storage will be checked during conservative root scanning. In other words, this allows you to put something like this in a ConservativeVector<Foo> and it will be protected from GC: struct Foo { i64 number; Value some_value; GCPtr<Object> some_object; };
2024-02-22 12:18:31 +00:00
for (auto& vector : m_conservative_vectors) {
for (auto possible_value : vector.possible_values()) {
add_possible_value(possible_pointers, possible_value, HeapRoot { .type = HeapRoot::Type::ConservativeVector }, min_block_address, max_block_address);
}
}
LibJS: Use a HashTable to identify potential cell pointers in GC scan Previously we would iterate over all the live HeapBlocks in order to learn if an arbitrary pointer-sized value was a pointer into a live HeapBlock. This was quite time-consuming. Instead of that, just put all the live HeapBlock*'s in a HashTable and identify pointers by doing a bit-masked lookup into the table.
2020-11-10 19:24:08 +00:00
HashTable<HeapBlock*> all_live_heap_blocks;
for_each_block([&](auto& block) {
all_live_heap_blocks.set(&block);
return IterationDecision::Continue;
});
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
for_each_cell_among_possible_pointers(all_live_heap_blocks, possible_pointers, [&](Cell* cell, FlatPtr possible_pointer) {
if (cell->state() == Cell::State::Live) {
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
dbgln_if(HEAP_DEBUG, " ?-> {}", (void const*)cell);
roots.set(cell, *possible_pointers.get(possible_pointer));
} else {
dbgln_if(HEAP_DEBUG, " #-> {}", (void const*)cell);
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
}
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
});
LibJS: Implement basic conservative garbage collection We now scan the stack and CPU registers for potential pointers into the GC heap, and include any valid Cell pointers in the set of roots. This works pretty well but we'll also need to solve marking of things passed to native functions, since those are currently in Vector<Value> and the Vector storage is on the heap (not scanned.)
2020-03-16 18:08:59 +00:00
}
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
class MarkingVisitor final : public Cell::Visitor {
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
public:
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
explicit MarkingVisitor(Heap& heap, HashMap<Cell*, HeapRoot> const& roots)
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
: m_heap(heap)
LibJS: Use a work queue instead of the C++ stack for the GC mark phase This fixes an issue where we'd run out of C++ stack while traversing large GC heap graphs.
2023-01-10 19:17:29 +00:00
{
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
m_heap.find_min_and_max_block_addresses(m_min_block_address, m_max_block_address);
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
m_heap.for_each_block([&](auto& block) {
m_all_live_heap_blocks.set(&block);
return IterationDecision::Continue;
});
LibJS: Add GC graph dumper This change introduces a very basic GC graph dumper. The `dump_graph()` function outputs JSON data that contains information about all nodes in the graph, including their class types and edges. Root nodes will have a property indicating their root type or source location if the root is captured by a SafeFunction. It would be useful to add source location for other types of roots in the future. Output JSON dump have following format: ```json "4908721208": { "class_name": "Accessor", "edges": [ "4909298232", "4909297976" ] }, "4907520440": { "root": "SafeFunction Optional Optional.h:137", "class_name": "Realm", "edges": [ "4908269624", "4924821560", "4908409240", "4908483960", "4924527672" ] }, "4908251320": { "class_name": "CSSStyleRule", "edges": [ "4908302648", "4925101656", "4908251192" ] }, ```
2023-08-17 13:34:19 +00:00
for (auto* root : roots.keys()) {
LibJS: Use a work queue instead of the C++ stack for the GC mark phase This fixes an issue where we'd run out of C++ stack while traversing large GC heap graphs.
2023-01-10 19:17:29 +00:00
visit(root);
}
}
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
virtual void visit_impl(Cell& cell) override
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
{
LibJS: Make Cell::Visitor::visit_impl() take a Cell& Passing a null cell pointer is not supported.
2021-05-25 16:39:01 +00:00
if (cell.is_marked())
LibJS: Make the GC marking phase cycle-proof Don't visit cells that are already marked. This prevents the marking phase from looping forever when two cells refer to each other. Also do the marking directly from the CellVisitor, removing another unnecessary phase of the collector. :^)
2020-03-09 21:11:22 +00:00
return;
LibJS: Fix broken dbgln_if(HEAP_DEBUG)
2021-05-25 17:44:32 +00:00
dbgln_if(HEAP_DEBUG, " ! {}", &cell);
LibJS+js+test-js: Add GC debug mode that keeps cells "alive" as zombies This patch adds a `-z` option to js and test-js. When run in this mode, garbage cells are never actually destroyed. We instead keep them around in a special zombie state. This allows us to validate that zombies don't get marked in future GC scans (since there were not supposed to be any more references!) :^) Cells get notified when they become a zombie (via did_become_zombie()) and this is used by WeakContainer cells to deregister themselves from the heap.
2021-09-11 14:44:40 +00:00
LibJS: Make Cell::Visitor::visit_impl() take a Cell& Passing a null cell pointer is not supported.
2021-05-25 16:39:01 +00:00
cell.set_marked(true);
LibJS: Use a work queue instead of the C++ stack for the GC mark phase This fixes an issue where we'd run out of C++ stack while traversing large GC heap graphs.
2023-01-10 19:17:29 +00:00
m_work_queue.append(cell);
}
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
virtual void visit_possible_values(ReadonlyBytes bytes) override
{
LibJS: Add source location for Handle nodes in GC graph dumper output With this change JS::Handle root nodes will contain source location where they were constructed like: ``` "94675029575744": { "root": "Handle activate_event_handler \ serenity/Userland/Libraries/LibWeb/DOM/EventTarget.cpp:564", "class_name": "HTMLButtonElement", "edges": [ "94675025955904", "94675026899520", "94675030831168", ```
2023-09-22 00:04:16 +00:00
HashMap<FlatPtr, HeapRoot> possible_pointers;
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
auto* raw_pointer_sized_values = reinterpret_cast<FlatPtr const*>(bytes.data());
for (size_t i = 0; i < (bytes.size() / sizeof(FlatPtr)); ++i)
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
add_possible_value(possible_pointers, raw_pointer_sized_values[i], HeapRoot { .type = HeapRoot::Type::HeapFunctionCapturedPointer }, m_min_block_address, m_max_block_address);
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
for_each_cell_among_possible_pointers(m_all_live_heap_blocks, possible_pointers, [&](Cell* cell, FlatPtr) {
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
if (cell->is_marked())
return;
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
if (cell->state() != Cell::State::Live)
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
return;
cell->set_marked(true);
m_work_queue.append(*cell);
});
}
LibJS: Use a work queue instead of the C++ stack for the GC mark phase This fixes an issue where we'd run out of C++ stack while traversing large GC heap graphs.
2023-01-10 19:17:29 +00:00
void mark_all_live_cells()
{
while (!m_work_queue.is_empty()) {
LibJS: Fix some GCVerifier warnings
2024-04-05 20:47:41 +00:00
m_work_queue.take_last()->visit_edges(*this);
LibJS: Use a work queue instead of the C++ stack for the GC mark phase This fixes an issue where we'd run out of C++ stack while traversing large GC heap graphs.
2023-01-10 19:17:29 +00:00
}
LibJS: Make the GC marking phase cycle-proof Don't visit cells that are already marked. This prevents the marking phase from looping forever when two cells refer to each other. Also do the marking directly from the CellVisitor, removing another unnecessary phase of the collector. :^)
2020-03-09 21:11:22 +00:00
}
LibJS: Use a work queue instead of the C++ stack for the GC mark phase This fixes an issue where we'd run out of C++ stack while traversing large GC heap graphs.
2023-01-10 19:17:29 +00:00
private:
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
Heap& m_heap;
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
Vector<Ref<Cell>> m_work_queue;
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
HashTable<HeapBlock*> m_all_live_heap_blocks;
LibJS: Early reject pointers outside of allocated blocks range in GC This change adds a check to discard pointers that are lower than the minimum address of all allocated blocks or higher than the maximum address of all blocks. By doing this we avoid executing plenty of set() operations on the HashMap in the add_possible_value(). With this change gather_conservative_roots() run 10x times faster in Speedometer React-Redux-TodoMVC test.
2023-09-29 17:14:11 +00:00
FlatPtr m_min_block_address;
FlatPtr m_max_block_address;
LibJS: Make the GC marking phase cycle-proof Don't visit cells that are already marked. This prevents the marking phase from looping forever when two cells refer to each other. Also do the marking directly from the CellVisitor, removing another unnecessary phase of the collector. :^)
2020-03-09 21:11:22 +00:00
};
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
void Heap::mark_live_cells(HashMap<Cell*, HeapRoot> const& roots)
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
{
LibJS: Use dbgln_if in Heap.cpp
2021-04-07 13:12:32 +00:00
dbgln_if(HEAP_DEBUG, "mark_live_cells:");
test-js: Add a mark_as_garbage method to force GC to collect that object This should fix the flaky tests of test-js. It also fixes the tests when running with the -g flag since the values will not be garbage collected too soon.
2021-09-07 15:14:05 +00:00
AK+LibJS: Introduce `JS::HeapFunction` This change introduces HeapFunction, which is intended to be used as a replacement for SafeFunction. The new type behaves like a regular GC-allocated object, which means it needs to be visited from visit_edges, and unlike SafeFunction, it does not create new roots for captured parameters. Co-Authored-By: Andreas Kling <kling@serenityos.org>
2023-08-18 16:21:33 +00:00
MarkingVisitor visitor(*this, roots);
LibJS/Bytecode: Make Bytecode::Interpreter participate in GC marking Since the relationship between VM and Bytecode::Interpreter is now clear, we can have VM ask the Interpreter for roots in the GC marking pass. This avoids having to register and unregister handles and MarkedVectors over and over. Since GeneratorObject can also own a RegisterWindow, we share the code in a RegisterWindow::visit_edges() helper. ~4% speed-up on Kraken/stanford-crypto-ccm.js :^)
2023-07-02 10:53:10 +00:00
LibJS: Use a work queue instead of the C++ stack for the GC mark phase This fixes an issue where we'd run out of C++ stack while traversing large GC heap graphs.
2023-01-10 19:17:29 +00:00
visitor.mark_all_live_cells();
Revert "LibJS: Remove "uprooting" mechanism from garbage collector" This reverts commit 6232ad3a0d44a3833c476d37bf4084d39a10a74b. Unfortunately this introduced some flakiness on CI, so it wasn't quite this simple.
2023-07-22 04:53:22 +00:00
for (auto& inverse_root : m_uprooted_cells)
inverse_root->set_marked(false);
m_uprooted_cells.clear();
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
}
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
bool Heap::cell_must_survive_garbage_collection(Cell const& cell)
LibJS: Add Cell::must_survive_garbage_collection() mechanism This allows cells to prevent themselves from being garbage collected, even when there are no references to them.
2022-10-24 10:37:54 +00:00
{
if (!cell.overrides_must_survive_garbage_collection({}))
return false;
return cell.must_survive_garbage_collection();
}
LibJS: Add a finalization pass to the garbage collector Doing things in the destructor of a GC-allocated object isn't always safe, in case it involves accessing other GC-allocated objects. If they were already swept by GC, we'd be poking into freed memory. This patch adds a separate finalization pass where GC calls finalize() on every unmarked cell that's about to be deleted. It's safe to access other GC objects in finalize(), even if they're also unmarked.
2022-10-20 16:35:19 +00:00
void Heap::finalize_unmarked_cells()
{
for_each_block([&](auto& block) {
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
block.template for_each_cell_in_state<Cell::State::Live>([](Cell* cell) {
LibJS: Add Cell::must_survive_garbage_collection() mechanism This allows cells to prevent themselves from being garbage collected, even when there are no references to them.
2022-10-24 10:37:54 +00:00
if (!cell->is_marked() && !cell_must_survive_garbage_collection(*cell))
LibJS: Add a finalization pass to the garbage collector Doing things in the destructor of a GC-allocated object isn't always safe, in case it involves accessing other GC-allocated objects. If they were already swept by GC, we'd be poking into freed memory. This patch adds a separate finalization pass where GC calls finalize() on every unmarked cell that's about to be deleted. It's safe to access other GC objects in finalize(), even if they're also unmarked.
2022-10-20 16:35:19 +00:00
cell->finalize();
});
return IterationDecision::Continue;
});
}
Everywhere: Run clang-format
2022-04-01 17:58:27 +00:00
void Heap::sweep_dead_cells(bool print_report, Core::ElapsedTimer const& measurement_timer)
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
{
LibJS: Use dbgln_if in Heap.cpp
2021-04-07 13:12:32 +00:00
dbgln_if(HEAP_DEBUG, "sweep_dead_cells:");
LibJS: Delete fully-empty HeapBlocks after garbage collection We now deallocate GC blocks when they are found to have no live cells inside them.
2020-03-21 10:45:50 +00:00
Vector<HeapBlock*, 32> empty_blocks;
LibJS: Split Heap into per-cell-size allocators Instead of keeping all the HeapBlocks in one big list, we now split it into two levels: - Heap has a set of Allocators, each with a specific cell size. - Allocators have two lists of blocks, "full" and "usable". Allocating a new cell no longer has to scan the entire set of blocks, but instead just needs to find the right allocator and then pop a cell from its freelist. If all the blocks in the allocator are full, a new block will be created. Blocks are moved from the "full" to "usable" list after sweeping has determined that they are not completely empty and not completely full. There are certainly many ways we can improve on this. This patch is mostly about getting the new allocator architecture in place. :^)
2020-10-06 16:50:47 +00:00
Vector<HeapBlock*, 32> full_blocks_that_became_usable;
LibJS: Delete fully-empty HeapBlocks after garbage collection We now deallocate GC blocks when they are found to have no live cells inside them.
2020-03-21 10:45:50 +00:00
LibJS: Add API for doing GC with a little debug log report at end You can now pass print_report=true to Heap::collect_garbage() and it will print out a little summary of the time spent, and counts of live vs freed cells and blocks.
2020-08-16 18:33:56 +00:00
size_t collected_cells = 0;
size_t live_cells = 0;
size_t collected_cell_bytes = 0;
size_t live_cell_bytes = 0;
LibJS: Split Heap into per-cell-size allocators Instead of keeping all the HeapBlocks in one big list, we now split it into two levels: - Heap has a set of Allocators, each with a specific cell size. - Allocators have two lists of blocks, "full" and "usable". Allocating a new cell no longer has to scan the entire set of blocks, but instead just needs to find the right allocator and then pop a cell from its freelist. If all the blocks in the allocator are full, a new block will be created. Blocks are moved from the "full" to "usable" list after sweeping has determined that they are not completely empty and not completely full. There are certainly many ways we can improve on this. This patch is mostly about getting the new allocator architecture in place. :^)
2020-10-06 16:50:47 +00:00
for_each_block([&](auto& block) {
LibJS: Delete fully-empty HeapBlocks after garbage collection We now deallocate GC blocks when they are found to have no live cells inside them.
2020-03-21 10:45:50 +00:00
bool block_has_live_cells = false;
LibJS: Split Heap into per-cell-size allocators Instead of keeping all the HeapBlocks in one big list, we now split it into two levels: - Heap has a set of Allocators, each with a specific cell size. - Allocators have two lists of blocks, "full" and "usable". Allocating a new cell no longer has to scan the entire set of blocks, but instead just needs to find the right allocator and then pop a cell from its freelist. If all the blocks in the allocator are full, a new block will be created. Blocks are moved from the "full" to "usable" list after sweeping has determined that they are not completely empty and not completely full. There are certainly many ways we can improve on this. This patch is mostly about getting the new allocator architecture in place. :^)
2020-10-06 16:50:47 +00:00
bool block_was_full = block.is_full();
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
block.template for_each_cell_in_state<Cell::State::Live>([&](Cell* cell) {
LibJS: Add Cell::must_survive_garbage_collection() mechanism This allows cells to prevent themselves from being garbage collected, even when there are no references to them.
2022-10-24 10:37:54 +00:00
if (!cell->is_marked() && !cell_must_survive_garbage_collection(*cell)) {
LibJS: Replace Cell live bit with a cell state So far we only have two states: Live and Dead. In the future, we can add additional states to support incremental sweeping and/or multi- stage cell destruction.
2021-05-25 16:35:27 +00:00
dbgln_if(HEAP_DEBUG, " ~ {}", cell);
LibJS: Remove the JS_TRACK_ZOMBIE_CELLS option This feature had bitrotted somewhat and would trigger errors because PrimitiveStrings were "destroyed" but because of this mode they were not removed from the string cache. Even fixing that case running test-js with the options still failed in more places.
2022-02-04 15:12:39 +00:00
block.deallocate(cell);
LibJS: Replace Cell live bit with a cell state So far we only have two states: Live and Dead. In the future, we can add additional states to support incremental sweeping and/or multi- stage cell destruction.
2021-05-25 16:35:27 +00:00
++collected_cells;
collected_cell_bytes += block.cell_size();
} else {
cell->set_marked(false);
block_has_live_cells = true;
++live_cells;
live_cell_bytes += block.cell_size();
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
}
});
LibJS: Delete fully-empty HeapBlocks after garbage collection We now deallocate GC blocks when they are found to have no live cells inside them.
2020-03-21 10:45:50 +00:00
if (!block_has_live_cells)
LibJS: Split Heap into per-cell-size allocators Instead of keeping all the HeapBlocks in one big list, we now split it into two levels: - Heap has a set of Allocators, each with a specific cell size. - Allocators have two lists of blocks, "full" and "usable". Allocating a new cell no longer has to scan the entire set of blocks, but instead just needs to find the right allocator and then pop a cell from its freelist. If all the blocks in the allocator are full, a new block will be created. Blocks are moved from the "full" to "usable" list after sweeping has determined that they are not completely empty and not completely full. There are certainly many ways we can improve on this. This patch is mostly about getting the new allocator architecture in place. :^)
2020-10-06 16:50:47 +00:00
empty_blocks.append(&block);
else if (block_was_full != block.is_full())
full_blocks_that_became_usable.append(&block);
return IterationDecision::Continue;
});
LibJS: Delete fully-empty HeapBlocks after garbage collection We now deallocate GC blocks when they are found to have no live cells inside them.
2020-03-21 10:45:50 +00:00
LibJS: Prune WeakContainers before freeing HeapBlocks WeakContainers need to look at the Cell::State bits to know if their weak pointees got swept by garbage collection. So we must do this before potentially freeing one or more HeapBlocks by notifying the allocator that a block became empty.
2021-10-08 17:47:25 +00:00
for (auto& weak_container : m_weak_containers)
weak_container.remove_dead_cells({});
LibJS: Delete fully-empty HeapBlocks after garbage collection We now deallocate GC blocks when they are found to have no live cells inside them.
2020-03-21 10:45:50 +00:00
for (auto* block : empty_blocks) {
LibJS: Use dbgln_if in Heap.cpp
2021-04-07 13:12:32 +00:00
dbgln_if(HEAP_DEBUG, " - HeapBlock empty @ {}: cell_size={}", block, block->cell_size());
LibJS: Make Heap aware of all CellAllocators Also add a link from HeapBlock to their owning CellAllocator. This fixes an issue where the Heap would skip over non-size-based cell allocators.
2023-12-23 14:13:51 +00:00
block->cell_allocator().block_did_become_empty({}, *block);
LibJS: Delete fully-empty HeapBlocks after garbage collection We now deallocate GC blocks when they are found to have no live cells inside them.
2020-03-21 10:45:50 +00:00
}
LibJS: Split Heap into per-cell-size allocators Instead of keeping all the HeapBlocks in one big list, we now split it into two levels: - Heap has a set of Allocators, each with a specific cell size. - Allocators have two lists of blocks, "full" and "usable". Allocating a new cell no longer has to scan the entire set of blocks, but instead just needs to find the right allocator and then pop a cell from its freelist. If all the blocks in the allocator are full, a new block will be created. Blocks are moved from the "full" to "usable" list after sweeping has determined that they are not completely empty and not completely full. There are certainly many ways we can improve on this. This patch is mostly about getting the new allocator architecture in place. :^)
2020-10-06 16:50:47 +00:00
for (auto* block : full_blocks_that_became_usable) {
LibJS: Use dbgln_if in Heap.cpp
2021-04-07 13:12:32 +00:00
dbgln_if(HEAP_DEBUG, " - HeapBlock usable again @ {}: cell_size={}", block, block->cell_size());
LibJS: Make Heap aware of all CellAllocators Also add a link from HeapBlock to their owning CellAllocator. This fixes an issue where the Heap would skip over non-size-based cell allocators.
2023-12-23 14:13:51 +00:00
block->cell_allocator().block_did_become_usable({}, *block);
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
}
LibJS: Split Heap into per-cell-size allocators Instead of keeping all the HeapBlocks in one big list, we now split it into two levels: - Heap has a set of Allocators, each with a specific cell size. - Allocators have two lists of blocks, "full" and "usable". Allocating a new cell no longer has to scan the entire set of blocks, but instead just needs to find the right allocator and then pop a cell from its freelist. If all the blocks in the allocator are full, a new block will be created. Blocks are moved from the "full" to "usable" list after sweeping has determined that they are not completely empty and not completely full. There are certainly many ways we can improve on this. This patch is mostly about getting the new allocator architecture in place. :^)
2020-10-06 16:50:47 +00:00
LibJS: Use 'if constexpr' instead of '#if HEAP_DEBUG'
2021-04-18 16:12:33 +00:00
if constexpr (HEAP_DEBUG) {
for_each_block([&](auto& block) {
dbgln(" > Live HeapBlock @ {}: cell_size={}", &block, block.cell_size());
return IterationDecision::Continue;
});
}
LibJS: Add API for doing GC with a little debug log report at end You can now pass print_report=true to Heap::collect_garbage() and it will print out a little summary of the time spent, and counts of live vs freed cells and blocks.
2020-08-16 18:33:56 +00:00
LibJS: Improve garbage collection trigger condition This patch triggers the collector when allocated memory doubles instead of every 100k allocations. Which can almost half (reduce by ~48%) the time spent on collection when loading google-maps. This dynamic approach is inspired by some other GCs like Golang's and Lua's and improves performance in memory heavy applications because marking must visit old objects which will dominate the marking phase if the GC is invoked too often. This commit also improves the Octane Splay benchmark and almost doubles it :^)
2023-08-08 17:50:32 +00:00
m_gc_bytes_threshold = live_cell_bytes > GC_MIN_BYTES_THRESHOLD ? live_cell_bytes : GC_MIN_BYTES_THRESHOLD;
LibJS: Add API for doing GC with a little debug log report at end You can now pass print_report=true to Heap::collect_garbage() and it will print out a little summary of the time spent, and counts of live vs freed cells and blocks.
2020-08-16 18:33:56 +00:00
if (print_report) {
LibJS: Prefix AK::Duration with AK Namespace
2024-07-17 05:45:00 +00:00
AK::Duration const time_spent = measurement_timer.elapsed_time();
LibJS: Split Heap into per-cell-size allocators Instead of keeping all the HeapBlocks in one big list, we now split it into two levels: - Heap has a set of Allocators, each with a specific cell size. - Allocators have two lists of blocks, "full" and "usable". Allocating a new cell no longer has to scan the entire set of blocks, but instead just needs to find the right allocator and then pop a cell from its freelist. If all the blocks in the allocator are full, a new block will be created. Blocks are moved from the "full" to "usable" list after sweeping has determined that they are not completely empty and not completely full. There are certainly many ways we can improve on this. This patch is mostly about getting the new allocator architecture in place. :^)
2020-10-06 16:50:47 +00:00
size_t live_block_count = 0;
for_each_block([&](auto&) {
++live_block_count;
return IterationDecision::Continue;
});
LibJS: Replace a few dbg() with dbgln()
2020-10-04 14:44:40 +00:00
dbgln("Garbage collection report");
dbgln("=============================================");
LibJS: Only start ElapsedTimer for GC metrics when printing is enabled We don't need to be checking the current time unconditionally when we only observe the results if we're going to dump the GC stats. This saves two trips to clock_gettime at the cost of an extra branch.
2023-01-02 05:45:28 +00:00
dbgln(" Time spent: {} ms", time_spent.to_milliseconds());
LibJS: Replace a few dbg() with dbgln()
2020-10-04 14:44:40 +00:00
dbgln(" Live cells: {} ({} bytes)", live_cells, live_cell_bytes);
dbgln("Collected cells: {} ({} bytes)", collected_cells, collected_cell_bytes);
LibJS: Split Heap into per-cell-size allocators Instead of keeping all the HeapBlocks in one big list, we now split it into two levels: - Heap has a set of Allocators, each with a specific cell size. - Allocators have two lists of blocks, "full" and "usable". Allocating a new cell no longer has to scan the entire set of blocks, but instead just needs to find the right allocator and then pop a cell from its freelist. If all the blocks in the allocator are full, a new block will be created. Blocks are moved from the "full" to "usable" list after sweeping has determined that they are not completely empty and not completely full. There are certainly many ways we can improve on this. This patch is mostly about getting the new allocator architecture in place. :^)
2020-10-06 16:50:47 +00:00
dbgln(" Live blocks: {} ({} bytes)", live_block_count, live_block_count * HeapBlock::block_size);
LibJS: Replace a few dbg() with dbgln()
2020-10-04 14:44:40 +00:00
dbgln(" Freed blocks: {} ({} bytes)", empty_blocks.size(), empty_blocks.size() * HeapBlock::block_size);
dbgln("=============================================");
LibJS: Add API for doing GC with a little debug log report at end You can now pass print_report=true to Heap::collect_garbage() and it will print out a little summary of the time spent, and counts of live vs freed cells and blocks.
2020-08-16 18:33:56 +00:00
}
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
}
LibJS: Add Handle<T>, a strong C++ handle for keeping GC objects alive This is pretty heavy and unoptimized, but it will do the trick for now. Basically, Heap now has a HashTable<HandleImpl*> and you can call JS::make_handle(T*) to construct a Handle<T> that guarantees that the pointee will always survive GC until the Handle<T> is destroyed.
2020-03-18 19:03:17 +00:00
LibJS: Make GC deferral friendship based
2023-09-23 11:44:13 +00:00
void Heap::defer_gc()
LibJS: Add DeferGC, a RAII way to prevent GC temporarily
2020-04-19 09:30:47 +00:00
{
++m_gc_deferrals;
}
LibJS: Make GC deferral friendship based
2023-09-23 11:44:13 +00:00
void Heap::undefer_gc()
LibJS: Add DeferGC, a RAII way to prevent GC temporarily
2020-04-19 09:30:47 +00:00
{
Everywhere: Rename ASSERT => VERIFY (...and ASSERT_NOT_REACHED => VERIFY_NOT_REACHED) Since all of these checks are done in release builds as well, let's rename them to VERIFY to prevent confusion, as everyone is used to assertions being compiled out in release. We can introduce a new ASSERT macro that is specifically for debug checks, but I'm doing this wholesale conversion first since we've accumulated thousands of these already, and it's not immediately obvious which ones are suitable for ASSERT.
2021-02-23 19:42:32 +00:00
VERIFY(m_gc_deferrals > 0);
LibJS: Add DeferGC, a RAII way to prevent GC temporarily
2020-04-19 09:30:47 +00:00
--m_gc_deferrals;
if (!m_gc_deferrals) {
if (m_should_gc_when_deferral_ends)
collect_garbage();
m_should_gc_when_deferral_ends = false;
}
}
LibGC+Everywhere: Factor out a LibGC from LibJS Resulting in a massive rename across almost everywhere! Alongside the namespace change, we now have the following names: * JS::NonnullGCPtr -> GC::Ref * JS::GCPtr -> GC::Ptr * JS::HeapFunction -> GC::Function * JS::CellImpl -> GC::Cell * JS::Handle -> GC::Root
2024-11-14 15:01:23 +00:00
void Heap::uproot_cell(Cell* cell)
Revert "LibJS: Remove "uprooting" mechanism from garbage collector" This reverts commit 6232ad3a0d44a3833c476d37bf4084d39a10a74b. Unfortunately this introduced some flakiness on CI, so it wasn't quite this simple.
2023-07-22 04:53:22 +00:00
{
m_uprooted_cells.append(cell);
}
LibJS: Add a basic mark&sweep garbage collector :^) Objects can now be allocated via the interpreter's heap. Objects that are allocated in this way will need to be provably reachable from at least one of the known object graph roots. The roots are currently determined by Heap::collect_roots(). Anything that wants be collectable garbage should inherit from Cell, the fundamental atom of the GC heap. This is pretty neat! :^)
2020-03-08 18:23:58 +00:00
}
Reference in a new issue Copy permalink