| // Copyright 2016 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_SLOT_SET_H |
| #define V8_SLOT_SET_H |
| |
| #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. |
| // The data structure assumes that the slots are pointer size aligned and |
| // splits the valid slot offset range into kBuckets buckets. |
| // Each bucket is a bitmap with a bit corresponding to a single slot offset. |
| class SlotSet : public Malloced { |
| public: |
| SlotSet() { |
| for (int i = 0; i < kBuckets; i++) { |
| bucket[i] = nullptr; |
| } |
| } |
| |
| ~SlotSet() { |
| for (int i = 0; i < kBuckets; i++) { |
| ReleaseBucket(i); |
| } |
| } |
| |
| void SetPageStart(Address page_start) { page_start_ = page_start; } |
| |
| // The slot offset specifies a slot at address page_start_ + slot_offset. |
| void Insert(int slot_offset) { |
| int bucket_index, cell_index, bit_index; |
| SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); |
| if (bucket[bucket_index] == nullptr) { |
| bucket[bucket_index] = AllocateBucket(); |
| } |
| bucket[bucket_index][cell_index] |= 1u << bit_index; |
| } |
| |
| // The slot offset specifies a slot at address page_start_ + slot_offset. |
| void Remove(int slot_offset) { |
| int bucket_index, cell_index, bit_index; |
| SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); |
| if (bucket[bucket_index] != nullptr) { |
| uint32_t cell = bucket[bucket_index][cell_index]; |
| if (cell) { |
| uint32_t bit_mask = 1u << bit_index; |
| if (cell & bit_mask) { |
| bucket[bucket_index][cell_index] ^= bit_mask; |
| } |
| } |
| } |
| } |
| |
| // The slot offsets specify a range of slots at addresses: |
| // [page_start_ + start_offset ... page_start_ + end_offset). |
| void RemoveRange(int start_offset, int end_offset) { |
| DCHECK_LE(start_offset, end_offset); |
| int start_bucket, start_cell, start_bit; |
| SlotToIndices(start_offset, &start_bucket, &start_cell, &start_bit); |
| int end_bucket, end_cell, end_bit; |
| SlotToIndices(end_offset, &end_bucket, &end_cell, &end_bit); |
| uint32_t start_mask = (1u << start_bit) - 1; |
| uint32_t end_mask = ~((1u << end_bit) - 1); |
| if (start_bucket == end_bucket && start_cell == end_cell) { |
| MaskCell(start_bucket, start_cell, start_mask | end_mask); |
| return; |
| } |
| int current_bucket = start_bucket; |
| int current_cell = start_cell; |
| MaskCell(current_bucket, current_cell, start_mask); |
| current_cell++; |
| if (current_bucket < end_bucket) { |
| if (bucket[current_bucket] != nullptr) { |
| while (current_cell < kCellsPerBucket) { |
| bucket[current_bucket][current_cell] = 0; |
| current_cell++; |
| } |
| } |
| // The rest of the current bucket is cleared. |
| // Move on to the next bucket. |
| current_bucket++; |
| current_cell = 0; |
| } |
| DCHECK(current_bucket == end_bucket || |
| (current_bucket < end_bucket && current_cell == 0)); |
| while (current_bucket < end_bucket) { |
| ReleaseBucket(current_bucket); |
| current_bucket++; |
| } |
| // All buckets between start_bucket and end_bucket are cleared. |
| DCHECK(current_bucket == end_bucket && current_cell <= end_cell); |
| if (current_bucket == kBuckets || bucket[current_bucket] == nullptr) { |
| return; |
| } |
| while (current_cell < end_cell) { |
| bucket[current_bucket][current_cell] = 0; |
| current_cell++; |
| } |
| // All cells between start_cell and end_cell are cleared. |
| DCHECK(current_bucket == end_bucket && current_cell == end_cell); |
| MaskCell(end_bucket, end_cell, end_mask); |
| } |
| |
| // The slot offset specifies a slot at address page_start_ + slot_offset. |
| bool Lookup(int slot_offset) { |
| int bucket_index, cell_index, bit_index; |
| SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); |
| if (bucket[bucket_index] != nullptr) { |
| uint32_t cell = bucket[bucket_index][cell_index]; |
| return (cell & (1u << bit_index)) != 0; |
| } |
| return false; |
| } |
| |
| // 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([](Address slot_address) { |
| // if (good(slot_address)) return KEEP_SLOT; |
| // else return REMOVE_SLOT; |
| // }); |
| template <typename Callback> |
| int Iterate(Callback callback) { |
| int new_count = 0; |
| for (int bucket_index = 0; bucket_index < kBuckets; bucket_index++) { |
| if (bucket[bucket_index] != nullptr) { |
| int in_bucket_count = 0; |
| uint32_t* current_bucket = bucket[bucket_index]; |
| int cell_offset = bucket_index * kBitsPerBucket; |
| for (int i = 0; i < kCellsPerBucket; i++, cell_offset += kBitsPerCell) { |
| if (current_bucket[i]) { |
| uint32_t cell = current_bucket[i]; |
| uint32_t old_cell = cell; |
| uint32_t new_cell = cell; |
| while (cell) { |
| int bit_offset = base::bits::CountTrailingZeros32(cell); |
| uint32_t bit_mask = 1u << bit_offset; |
| uint32_t slot = (cell_offset + bit_offset) << kPointerSizeLog2; |
| if (callback(page_start_ + slot) == KEEP_SLOT) { |
| ++in_bucket_count; |
| } else { |
| new_cell ^= bit_mask; |
| } |
| cell ^= bit_mask; |
| } |
| if (old_cell != new_cell) { |
| current_bucket[i] = new_cell; |
| } |
| } |
| } |
| if (in_bucket_count == 0) { |
| ReleaseBucket(bucket_index); |
| } |
| new_count += in_bucket_count; |
| } |
| } |
| return new_count; |
| } |
| |
| private: |
| static const int kMaxSlots = (1 << kPageSizeBits) / kPointerSize; |
| static const int kCellsPerBucket = 32; |
| static const int kCellsPerBucketLog2 = 5; |
| static const int kBitsPerCell = 32; |
| static const int kBitsPerCellLog2 = 5; |
| static const int kBitsPerBucket = kCellsPerBucket * kBitsPerCell; |
| static const int kBitsPerBucketLog2 = kCellsPerBucketLog2 + kBitsPerCellLog2; |
| static const int kBuckets = kMaxSlots / kCellsPerBucket / kBitsPerCell; |
| |
| uint32_t* AllocateBucket() { |
| uint32_t* result = NewArray<uint32_t>(kCellsPerBucket); |
| for (int i = 0; i < kCellsPerBucket; i++) { |
| result[i] = 0; |
| } |
| return result; |
| } |
| |
| void ReleaseBucket(int bucket_index) { |
| DeleteArray<uint32_t>(bucket[bucket_index]); |
| bucket[bucket_index] = nullptr; |
| } |
| |
| void MaskCell(int bucket_index, int cell_index, uint32_t mask) { |
| uint32_t* cells = bucket[bucket_index]; |
| if (cells != nullptr && cells[cell_index] != 0) { |
| cells[cell_index] &= mask; |
| } |
| } |
| |
| // Converts the slot offset into bucket/cell/bit index. |
| void SlotToIndices(int slot_offset, int* bucket_index, int* cell_index, |
| int* bit_index) { |
| DCHECK_EQ(slot_offset % kPointerSize, 0); |
| int slot = slot_offset >> kPointerSizeLog2; |
| DCHECK(slot >= 0 && slot <= kMaxSlots); |
| *bucket_index = slot >> kBitsPerBucketLog2; |
| *cell_index = (slot >> kBitsPerCellLog2) & (kCellsPerBucket - 1); |
| *bit_index = slot & (kBitsPerCell - 1); |
| } |
| |
| uint32_t* bucket[kBuckets]; |
| 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 |
| |
| #endif // V8_SLOT_SET_H |