Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 1 | // Copyright 2015 the V8 project authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #ifndef V8_HEAP_SLOTS_BUFFER_H_ |
| 6 | #define V8_HEAP_SLOTS_BUFFER_H_ |
| 7 | |
| 8 | #include "src/objects.h" |
| 9 | |
| 10 | namespace v8 { |
| 11 | namespace internal { |
| 12 | |
| 13 | // Forward declarations. |
| 14 | class SlotsBuffer; |
| 15 | |
| 16 | |
| 17 | // SlotsBufferAllocator manages the allocation and deallocation of slots buffer |
| 18 | // chunks and links them together. Slots buffer chunks are always created by the |
| 19 | // SlotsBufferAllocator. |
| 20 | class SlotsBufferAllocator { |
| 21 | public: |
| 22 | SlotsBuffer* AllocateBuffer(SlotsBuffer* next_buffer); |
| 23 | void DeallocateBuffer(SlotsBuffer* buffer); |
| 24 | |
| 25 | void DeallocateChain(SlotsBuffer** buffer_address); |
| 26 | }; |
| 27 | |
| 28 | |
| 29 | // SlotsBuffer records a sequence of slots that has to be updated |
| 30 | // after live objects were relocated from evacuation candidates. |
| 31 | // All slots are either untyped or typed: |
| 32 | // - Untyped slots are expected to contain a tagged object pointer. |
| 33 | // They are recorded by an address. |
| 34 | // - Typed slots are expected to contain an encoded pointer to a heap |
| 35 | // object where the way of encoding depends on the type of the slot. |
| 36 | // They are recorded as a pair (SlotType, slot address). |
| 37 | // We assume that zero-page is never mapped this allows us to distinguish |
| 38 | // untyped slots from typed slots during iteration by a simple comparison: |
| 39 | // if element of slots buffer is less than NUMBER_OF_SLOT_TYPES then it |
| 40 | // is the first element of typed slot's pair. |
| 41 | class SlotsBuffer { |
| 42 | public: |
| 43 | typedef Object** ObjectSlot; |
| 44 | |
| 45 | explicit SlotsBuffer(SlotsBuffer* next_buffer) |
| 46 | : idx_(0), chain_length_(1), next_(next_buffer) { |
| 47 | if (next_ != NULL) { |
| 48 | chain_length_ = next_->chain_length_ + 1; |
| 49 | } |
| 50 | } |
| 51 | |
| 52 | ~SlotsBuffer() {} |
| 53 | |
| 54 | void Add(ObjectSlot slot) { |
| 55 | DCHECK(0 <= idx_ && idx_ < kNumberOfElements); |
| 56 | #ifdef DEBUG |
| 57 | if (slot >= reinterpret_cast<ObjectSlot>(NUMBER_OF_SLOT_TYPES)) { |
| 58 | DCHECK_NOT_NULL(*slot); |
| 59 | } |
| 60 | #endif |
| 61 | slots_[idx_++] = slot; |
| 62 | } |
| 63 | |
| 64 | ObjectSlot Get(intptr_t i) { |
| 65 | DCHECK(i >= 0 && i < kNumberOfElements); |
| 66 | return slots_[i]; |
| 67 | } |
| 68 | |
| 69 | size_t Size() { |
| 70 | DCHECK(idx_ <= kNumberOfElements); |
| 71 | return idx_; |
| 72 | } |
| 73 | |
| 74 | enum SlotType { |
| 75 | EMBEDDED_OBJECT_SLOT, |
| 76 | OBJECT_SLOT, |
| 77 | RELOCATED_CODE_OBJECT, |
| 78 | CELL_TARGET_SLOT, |
| 79 | CODE_TARGET_SLOT, |
| 80 | CODE_ENTRY_SLOT, |
| 81 | DEBUG_TARGET_SLOT, |
| 82 | NUMBER_OF_SLOT_TYPES |
| 83 | }; |
| 84 | |
| 85 | static const char* SlotTypeToString(SlotType type) { |
| 86 | switch (type) { |
| 87 | case EMBEDDED_OBJECT_SLOT: |
| 88 | return "EMBEDDED_OBJECT_SLOT"; |
| 89 | case OBJECT_SLOT: |
| 90 | return "OBJECT_SLOT"; |
| 91 | case RELOCATED_CODE_OBJECT: |
| 92 | return "RELOCATED_CODE_OBJECT"; |
| 93 | case CELL_TARGET_SLOT: |
| 94 | return "CELL_TARGET_SLOT"; |
| 95 | case CODE_TARGET_SLOT: |
| 96 | return "CODE_TARGET_SLOT"; |
| 97 | case CODE_ENTRY_SLOT: |
| 98 | return "CODE_ENTRY_SLOT"; |
| 99 | case DEBUG_TARGET_SLOT: |
| 100 | return "DEBUG_TARGET_SLOT"; |
| 101 | case NUMBER_OF_SLOT_TYPES: |
| 102 | return "NUMBER_OF_SLOT_TYPES"; |
| 103 | } |
| 104 | return "UNKNOWN SlotType"; |
| 105 | } |
| 106 | |
| 107 | SlotsBuffer* next() { return next_; } |
| 108 | |
| 109 | static int SizeOfChain(SlotsBuffer* buffer) { |
| 110 | if (buffer == NULL) return 0; |
| 111 | return static_cast<int>(buffer->idx_ + |
| 112 | (buffer->chain_length_ - 1) * kNumberOfElements); |
| 113 | } |
| 114 | |
| 115 | inline bool IsFull() { return idx_ == kNumberOfElements; } |
| 116 | |
| 117 | inline bool HasSpaceForTypedSlot() { return idx_ < kNumberOfElements - 1; } |
| 118 | |
| 119 | enum AdditionMode { FAIL_ON_OVERFLOW, IGNORE_OVERFLOW }; |
| 120 | |
| 121 | static bool ChainLengthThresholdReached(SlotsBuffer* buffer) { |
| 122 | return buffer != NULL && buffer->chain_length_ >= kChainLengthThreshold; |
| 123 | } |
| 124 | |
| 125 | INLINE(static bool AddTo(SlotsBufferAllocator* allocator, |
| 126 | SlotsBuffer** buffer_address, ObjectSlot slot, |
| 127 | AdditionMode mode)) { |
| 128 | SlotsBuffer* buffer = *buffer_address; |
| 129 | if (buffer == NULL || buffer->IsFull()) { |
| 130 | if (mode == FAIL_ON_OVERFLOW && ChainLengthThresholdReached(buffer)) { |
| 131 | allocator->DeallocateChain(buffer_address); |
| 132 | return false; |
| 133 | } |
| 134 | buffer = allocator->AllocateBuffer(buffer); |
| 135 | *buffer_address = buffer; |
| 136 | } |
| 137 | buffer->Add(slot); |
| 138 | return true; |
| 139 | } |
| 140 | |
| 141 | static bool IsTypedSlot(ObjectSlot slot); |
| 142 | |
| 143 | static bool AddTo(SlotsBufferAllocator* allocator, |
| 144 | SlotsBuffer** buffer_address, SlotType type, Address addr, |
| 145 | AdditionMode mode); |
| 146 | |
| 147 | // Eliminates all stale entries from the slots buffer, i.e., slots that |
| 148 | // are not part of live objects anymore. This method must be called after |
| 149 | // marking, when the whole transitive closure is known and must be called |
| 150 | // before sweeping when mark bits are still intact. |
| 151 | static void RemoveInvalidSlots(Heap* heap, SlotsBuffer* buffer); |
| 152 | |
| 153 | // Eliminate all slots that are within the given address range. |
| 154 | static void RemoveObjectSlots(Heap* heap, SlotsBuffer* buffer, |
| 155 | Address start_slot, Address end_slot); |
| 156 | |
| 157 | // Ensures that there are no invalid slots in the chain of slots buffers. |
| 158 | static void VerifySlots(Heap* heap, SlotsBuffer* buffer); |
| 159 | |
| 160 | static const int kNumberOfElements = 1021; |
| 161 | |
| 162 | private: |
| 163 | static const int kChainLengthThreshold = 15; |
| 164 | |
| 165 | intptr_t idx_; |
| 166 | intptr_t chain_length_; |
| 167 | SlotsBuffer* next_; |
| 168 | ObjectSlot slots_[kNumberOfElements]; |
| 169 | }; |
| 170 | |
| 171 | |
| 172 | } // namespace internal |
| 173 | } // namespace v8 |
| 174 | |
| 175 | #endif // V8_HEAP_SLOTS_BUFFER_H_ |