src/sandbox/compactible-external-entity-table.h - v8/v8 - Git at Google

 // 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;
     friend class CppHeapPointerTable;

     // 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_
	// 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;
	friend class CppHeapPointerTable;

	// 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_