Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(570)

Unified Diff: src/heap/slot-set.h

Issue 1735523002: Reland "Replace slots buffer with remembered set. (patchset #14 id:250001 of https://codereview.chr… (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: one more int->size_t Created 4 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/heap/remembered-set.cc ('k') | src/heap/slots-buffer.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/heap/slot-set.h
diff --git a/src/heap/slot-set.h b/src/heap/slot-set.h
index 6144706f71e3ed34d81693557b4fe87492499619..e55ffe98e60aa88f74c2e886f226f37eb21bab93 100644
--- a/src/heap/slot-set.h
+++ b/src/heap/slot-set.h
@@ -7,10 +7,13 @@
#include "src/allocation.h"
#include "src/base/bits.h"
+#include "src/utils.h"
namespace v8 {
namespace internal {
+enum SlotCallbackResult { KEEP_SLOT, REMOVE_SLOT };
+
// Data structure for maintaining a set of slots in a standard (non-large)
// page. The base address of the page must be set with SetPageStart before any
// operation.
@@ -19,8 +22,6 @@ namespace internal {
// Each bucket is a bitmap with a bit corresponding to a single slot offset.
class SlotSet : public Malloced {
public:
- enum CallbackResult { KEEP_SLOT, REMOVE_SLOT };
-
SlotSet() {
for (int i = 0; i < kBuckets; i++) {
bucket[i] = nullptr;
@@ -213,6 +214,124 @@ class SlotSet : public Malloced {
Address page_start_;
};
+enum SlotType {
+ EMBEDDED_OBJECT_SLOT,
+ OBJECT_SLOT,
+ RELOCATED_CODE_OBJECT,
+ CELL_TARGET_SLOT,
+ CODE_TARGET_SLOT,
+ CODE_ENTRY_SLOT,
+ DEBUG_TARGET_SLOT,
+ NUMBER_OF_SLOT_TYPES
+};
+
+// Data structure for maintaining a multiset of typed slots in a page.
+// Typed slots can only appear in Code and JSFunction objects, so
+// the maximum possible offset is limited by the LargePage::kMaxCodePageSize.
+// The implementation is a chain of chunks, where each chunks is an array of
+// encoded (slot type, slot offset) pairs.
+// There is no duplicate detection and we do not expect many duplicates because
+// typed slots contain V8 internal pointers that are not directly exposed to JS.
+class TypedSlotSet {
+ public:
+ typedef uint32_t TypedSlot;
+ static const int kMaxOffset = 1 << 29;
+
+ explicit TypedSlotSet(Address page_start) : page_start_(page_start) {
+ chunk_ = new Chunk(nullptr, kInitialBufferSize);
+ }
+
+ ~TypedSlotSet() {
+ Chunk* chunk = chunk_;
+ while (chunk != nullptr) {
+ Chunk* next = chunk->next;
+ delete chunk;
+ chunk = next;
+ }
+ }
+
+ // The slot offset specifies a slot at address page_start_ + offset.
+ void Insert(SlotType type, int offset) {
+ TypedSlot slot = ToTypedSlot(type, offset);
+ if (!chunk_->AddSlot(slot)) {
+ chunk_ = new Chunk(chunk_, NextCapacity(chunk_->capacity));
+ bool added = chunk_->AddSlot(slot);
+ DCHECK(added);
+ USE(added);
+ }
+ }
+
+ // Iterate over all slots in the set and for each slot invoke the callback.
+ // If the callback returns REMOVE_SLOT then the slot is removed from the set.
+ // Returns the new number of slots.
+ //
+ // Sample usage:
+ // Iterate([](SlotType slot_type, Address slot_address) {
+ // if (good(slot_type, slot_address)) return KEEP_SLOT;
+ // else return REMOVE_SLOT;
+ // });
+ template <typename Callback>
+ int Iterate(Callback callback) {
+ STATIC_ASSERT(NUMBER_OF_SLOT_TYPES < 8);
+ const TypedSlot kRemovedSlot = TypeField::encode(NUMBER_OF_SLOT_TYPES);
+ Chunk* chunk = chunk_;
+ int new_count = 0;
+ while (chunk != nullptr) {
+ TypedSlot* buffer = chunk->buffer;
+ int count = chunk->count;
+ for (int i = 0; i < count; i++) {
+ TypedSlot slot = buffer[i];
+ if (slot != kRemovedSlot) {
+ SlotType type = TypeField::decode(slot);
+ Address addr = page_start_ + OffsetField::decode(slot);
+ if (callback(type, addr) == KEEP_SLOT) {
+ new_count++;
+ } else {
+ buffer[i] = kRemovedSlot;
+ }
+ }
+ }
+ chunk = chunk->next;
+ }
+ return new_count;
+ }
+
+ private:
+ static const int kInitialBufferSize = 100;
+ static const int kMaxBufferSize = 16 * KB;
+
+ static int NextCapacity(int capacity) {
+ return Min(kMaxBufferSize, capacity * 2);
+ }
+
+ static TypedSlot ToTypedSlot(SlotType type, int offset) {
+ return TypeField::encode(type) | OffsetField::encode(offset);
+ }
+
+ class OffsetField : public BitField<int, 0, 29> {};
+ class TypeField : public BitField<SlotType, 29, 3> {};
+
+ struct Chunk : Malloced {
+ explicit Chunk(Chunk* next_chunk, int capacity)
+ : next(next_chunk), count(0), capacity(capacity) {
+ buffer = NewArray<TypedSlot>(capacity);
+ }
+ bool AddSlot(TypedSlot slot) {
+ if (count == capacity) return false;
+ buffer[count++] = slot;
+ return true;
+ }
+ ~Chunk() { DeleteArray(buffer); }
+ Chunk* next;
+ int count;
+ int capacity;
+ TypedSlot* buffer;
+ };
+
+ Address page_start_;
+ Chunk* chunk_;
+};
+
} // namespace internal
} // namespace v8
« no previous file with comments | « src/heap/remembered-set.cc ('k') | src/heap/slots-buffer.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698