blob: b90abf0277381f430646cf2f1759ecab9ef32905 [file] [log] [blame]
// Copyright 2024 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_SANDBOX_COMPACTIBLE_EXTERNAL_ENTITY_TABLE_H_
#define V8_SANDBOX_COMPACTIBLE_EXTERNAL_ENTITY_TABLE_H_
#include "include/v8config.h"
#include "src/common/globals.h"
#include "src/sandbox/external-entity-table.h"
#ifdef V8_COMPRESS_POINTERS
namespace v8 {
namespace internal {
class Isolate;
class Histogram;
// Outcome of external pointer table compaction to use for the
// ExternalPointerTableCompactionOutcome histogram.
enum class ExternalEntityTableCompactionOutcome {
kSuccess = 0, // Compaction was successful.
// Outcome 1, partial success, is no longer supported.
kAborted = 2, // Compaction was aborted because the freelist grew too short.
};
/**
* An intermediate table class that abstracts garbage collection mechanism
* for pointer tables that support compaction.
*
* Table compaction:
* -----------------
* The table's spaces are to some degree self-compacting: since the freelists
* are sorted in ascending order, segments at the start of the table will
* usually be fairly well utilized, while later segments might become
* completely free, in which case they will be deallocated.
* However, as a single live entry may keep an entire segment alive, the
* following simple algorithm is used to compact a space if that is deemed
* necessary:
* - At the start of the GC marking phase, determine if a space needs to be
* compacted. This decision is mostly based on the absolute and relative
* size of the freelist.
* - If compaction is needed, this algorithm determines by how many segments
* it would like to shrink the space (N). It will then attempts to move all
* live entries out of these segments so that they can be deallocated
* afterwards during sweeping.
* - The algorithm then simply selects the last N segments for evacuation, and
* it "marks" them for evacuation simply by remembering the start of the
* first selected segment. Everything after this threshold value then
* becomes the evacuation area. In this way, it becomes very cheap to test
* if an entry or segment should be evacuated: only a single integer
* comparison against the threshold is required. It also establishes a
* simple compaction invariant: compaction always moves an entry at or above
* the threshold to a new position before the threshold.
* - During marking, whenever a live entry inside the evacuation area is
* found, a new "evacuation entry" is allocated from the freelist (which is
* assumed to have enough free slots) and the address of the handle in the
* object owning the table entry is written into it.
* - During sweeping, these evacuation entries are resolved: the content of
* the old entry is copied into the new entry and the handle in the object
* is updated to point to the new entry.
*
* When compacting, it is expected that the evacuation area contains few live
* entries and that the freelist will be able to serve all evacuation entry
* allocations. In that case, compaction is essentially free (very little
* marking overhead, no memory overhead). However, it can happen that the
* application allocates a large number of table entries during marking, in
* which case we might end up allocating new entries inside the evacuation area
* or even allocate entire new segments for the space that's being compacted.
* If that situation is detected, compaction is aborted during marking.
*
* This algorithm assumes that table entries (except for the null entry) are
* never shared between multiple objects. Otherwise, the following could
* happen: object A initially has handle H1 and is scanned during incremental
* marking. Next, object B with handle H2 is scanned and marked for
* evacuation. Afterwards, object A copies the handle H2 from object B.
* During sweeping, only object B's handle will be updated to point to the
* new entry while object A's handle is now dangling. If shared entries ever
* become necessary, setting pointer handles would have to be guarded by
* write barriers to avoid this scenario.
*/
template <typename Entry, size_t size>
class V8_EXPORT_PRIVATE CompactibleExternalEntityTable
: public ExternalEntityTable<Entry, size> {
using Base = ExternalEntityTable<Entry, size>;
public:
struct CompactionResult {
uint32_t start_of_evacuation_area;
bool success;
};
CompactibleExternalEntityTable() = default;
CompactibleExternalEntityTable(const CompactibleExternalEntityTable&) =
delete;
CompactibleExternalEntityTable& operator=(
const CompactibleExternalEntityTable&) = delete;
// The Spaces used by pointer tables also contain the state related
// to compaction.
struct Space : public Base::Space {
public:
Space() : start_of_evacuation_area_(kNotCompactingMarker) {}
// Determine if compaction is needed and if so start the compaction.
// This is expected to be called at the start of the GC marking phase.
void StartCompactingIfNeeded();
private:
friend class CompactibleExternalEntityTable<Entry, size>;
friend class ExternalPointerTable;
friend class ExternalBufferTable;
// Routines for compaction. See the comment about table compaction above.
inline bool IsCompacting();
inline void StartCompacting(uint32_t start_of_evacuation_area);
inline void StopCompacting();
inline void AbortCompacting(uint32_t start_of_evacuation_area);
inline bool CompactingWasAborted();
inline bool FieldWasInvalidated(Address field_address) const;
inline void ClearInvalidatedFields();
inline void AddInvalidatedField(Address field_address);
// This value indicates that this space is not currently being compacted. It
// is set to uint32_t max so that determining whether an entry should be
// evacuated becomes a single comparison:
// `bool should_be_evacuated = index >= start_of_evacuation_area`.
static constexpr uint32_t kNotCompactingMarker =
std::numeric_limits<uint32_t>::max();
// This value may be ORed into the start of evacuation area threshold
// during the GC marking phase to indicate that compaction has been
// aborted because the freelist grew too short and so evacuation entry
// allocation is no longer possible. This will prevent any further
// evacuation attempts as entries will be evacuated if their index is at or
// above the start of the evacuation area, which is now a huge value.
static constexpr uint32_t kCompactionAbortedMarker = 0xf0000000;
// When compacting this space, this field contains the index of the first
// entry in the evacuation area. The evacuation area then consists of all
// segments above this threshold, and the goal of compaction is to move all
// live entries out of these segments so that they can be deallocated after
// sweeping. The field can have the following values:
// - kNotCompactingMarker: compaction is not currently running.
// - A kEntriesPerSegment aligned value within: compaction is running and
// all entries after this value should be evacuated.
// - A value that has kCompactionAbortedMarker in its top bits:
// compaction has been aborted during marking. The original start of the
// evacuation area is still contained in the lower bits.
std::atomic<uint32_t> start_of_evacuation_area_;
// List of external pointer fields that have been invalidated.
// Only used when table compaction is running.
// We expect very few (usually none at all) fields to be invalidated during
// a GC, so a std::vector is probably better than a std::set or similar.
std::vector<Address> invalidated_fields_;
// Mutex guarding access to the invalidated_fields_ set.
base::Mutex invalidated_fields_mutex_;
};
// Allocate an EPT entry from the space's freelist, or add a freshly-allocated
// segment to the space and allocate there. If the space is compacting but
// the new index is above the evacuation threshold, abort compaction.
inline uint32_t AllocateEntry(Space* space);
CompactionResult FinishCompaction(Space* space, Histogram* counter);
inline void MaybeCreateEvacuationEntry(Space* space, uint32_t index,
Address handle_location);
};
} // namespace internal
} // namespace v8
#endif // V8_COMPRESS_POINTERS
#endif // V8_SANDBOX_COMPACTIBLE_EXTERNAL_ENTITY_TABLE_H_