1 // Copyright 2016 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_SLOT_SET_H 6 #define V8_SLOT_SET_H 7 8 #include "src/allocation.h" 9 #include "src/base/bits.h" 10 #include "src/utils.h" 11 12 namespace v8 { 13 namespace internal { 14 15 enum SlotCallbackResult { KEEP_SLOT, REMOVE_SLOT }; 16 17 // Data structure for maintaining a set of slots in a standard (non-large) 18 // page. The base address of the page must be set with SetPageStart before any 19 // operation. 20 // The data structure assumes that the slots are pointer size aligned and 21 // splits the valid slot offset range into kBuckets buckets. 22 // Each bucket is a bitmap with a bit corresponding to a single slot offset. 23 class SlotSet : public Malloced { 24 public: SlotSet()25 SlotSet() { 26 for (int i = 0; i < kBuckets; i++) { 27 bucket[i] = nullptr; 28 } 29 } 30 ~SlotSet()31 ~SlotSet() { 32 for (int i = 0; i < kBuckets; i++) { 33 ReleaseBucket(i); 34 } 35 } 36 SetPageStart(Address page_start)37 void SetPageStart(Address page_start) { page_start_ = page_start; } 38 39 // The slot offset specifies a slot at address page_start_ + slot_offset. Insert(int slot_offset)40 void Insert(int slot_offset) { 41 int bucket_index, cell_index, bit_index; 42 SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); 43 if (bucket[bucket_index] == nullptr) { 44 bucket[bucket_index] = AllocateBucket(); 45 } 46 bucket[bucket_index][cell_index] |= 1u << bit_index; 47 } 48 49 // The slot offset specifies a slot at address page_start_ + slot_offset. Remove(int slot_offset)50 void Remove(int slot_offset) { 51 int bucket_index, cell_index, bit_index; 52 SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); 53 if (bucket[bucket_index] != nullptr) { 54 uint32_t cell = bucket[bucket_index][cell_index]; 55 if (cell) { 56 uint32_t bit_mask = 1u << bit_index; 57 if (cell & bit_mask) { 58 bucket[bucket_index][cell_index] ^= bit_mask; 59 } 60 } 61 } 62 } 63 64 // The slot offsets specify a range of slots at addresses: 65 // [page_start_ + start_offset ... page_start_ + end_offset). RemoveRange(int start_offset,int end_offset)66 void RemoveRange(int start_offset, int end_offset) { 67 DCHECK_LE(start_offset, end_offset); 68 int start_bucket, start_cell, start_bit; 69 SlotToIndices(start_offset, &start_bucket, &start_cell, &start_bit); 70 int end_bucket, end_cell, end_bit; 71 SlotToIndices(end_offset, &end_bucket, &end_cell, &end_bit); 72 uint32_t start_mask = (1u << start_bit) - 1; 73 uint32_t end_mask = ~((1u << end_bit) - 1); 74 if (start_bucket == end_bucket && start_cell == end_cell) { 75 MaskCell(start_bucket, start_cell, start_mask | end_mask); 76 return; 77 } 78 int current_bucket = start_bucket; 79 int current_cell = start_cell; 80 MaskCell(current_bucket, current_cell, start_mask); 81 current_cell++; 82 if (current_bucket < end_bucket) { 83 if (bucket[current_bucket] != nullptr) { 84 while (current_cell < kCellsPerBucket) { 85 bucket[current_bucket][current_cell] = 0; 86 current_cell++; 87 } 88 } 89 // The rest of the current bucket is cleared. 90 // Move on to the next bucket. 91 current_bucket++; 92 current_cell = 0; 93 } 94 DCHECK(current_bucket == end_bucket || 95 (current_bucket < end_bucket && current_cell == 0)); 96 while (current_bucket < end_bucket) { 97 ReleaseBucket(current_bucket); 98 current_bucket++; 99 } 100 // All buckets between start_bucket and end_bucket are cleared. 101 DCHECK(current_bucket == end_bucket && current_cell <= end_cell); 102 if (current_bucket == kBuckets || bucket[current_bucket] == nullptr) { 103 return; 104 } 105 while (current_cell < end_cell) { 106 bucket[current_bucket][current_cell] = 0; 107 current_cell++; 108 } 109 // All cells between start_cell and end_cell are cleared. 110 DCHECK(current_bucket == end_bucket && current_cell == end_cell); 111 MaskCell(end_bucket, end_cell, end_mask); 112 } 113 114 // The slot offset specifies a slot at address page_start_ + slot_offset. Lookup(int slot_offset)115 bool Lookup(int slot_offset) { 116 int bucket_index, cell_index, bit_index; 117 SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); 118 if (bucket[bucket_index] != nullptr) { 119 uint32_t cell = bucket[bucket_index][cell_index]; 120 return (cell & (1u << bit_index)) != 0; 121 } 122 return false; 123 } 124 125 // Iterate over all slots in the set and for each slot invoke the callback. 126 // If the callback returns REMOVE_SLOT then the slot is removed from the set. 127 // Returns the new number of slots. 128 // 129 // Sample usage: 130 // Iterate([](Address slot_address) { 131 // if (good(slot_address)) return KEEP_SLOT; 132 // else return REMOVE_SLOT; 133 // }); 134 template <typename Callback> Iterate(Callback callback)135 int Iterate(Callback callback) { 136 int new_count = 0; 137 for (int bucket_index = 0; bucket_index < kBuckets; bucket_index++) { 138 if (bucket[bucket_index] != nullptr) { 139 int in_bucket_count = 0; 140 uint32_t* current_bucket = bucket[bucket_index]; 141 int cell_offset = bucket_index * kBitsPerBucket; 142 for (int i = 0; i < kCellsPerBucket; i++, cell_offset += kBitsPerCell) { 143 if (current_bucket[i]) { 144 uint32_t cell = current_bucket[i]; 145 uint32_t old_cell = cell; 146 uint32_t new_cell = cell; 147 while (cell) { 148 int bit_offset = base::bits::CountTrailingZeros32(cell); 149 uint32_t bit_mask = 1u << bit_offset; 150 uint32_t slot = (cell_offset + bit_offset) << kPointerSizeLog2; 151 if (callback(page_start_ + slot) == KEEP_SLOT) { 152 ++in_bucket_count; 153 } else { 154 new_cell ^= bit_mask; 155 } 156 cell ^= bit_mask; 157 } 158 if (old_cell != new_cell) { 159 current_bucket[i] = new_cell; 160 } 161 } 162 } 163 if (in_bucket_count == 0) { 164 ReleaseBucket(bucket_index); 165 } 166 new_count += in_bucket_count; 167 } 168 } 169 return new_count; 170 } 171 172 private: 173 static const int kMaxSlots = (1 << kPageSizeBits) / kPointerSize; 174 static const int kCellsPerBucket = 32; 175 static const int kCellsPerBucketLog2 = 5; 176 static const int kBitsPerCell = 32; 177 static const int kBitsPerCellLog2 = 5; 178 static const int kBitsPerBucket = kCellsPerBucket * kBitsPerCell; 179 static const int kBitsPerBucketLog2 = kCellsPerBucketLog2 + kBitsPerCellLog2; 180 static const int kBuckets = kMaxSlots / kCellsPerBucket / kBitsPerCell; 181 AllocateBucket()182 uint32_t* AllocateBucket() { 183 uint32_t* result = NewArray<uint32_t>(kCellsPerBucket); 184 for (int i = 0; i < kCellsPerBucket; i++) { 185 result[i] = 0; 186 } 187 return result; 188 } 189 ReleaseBucket(int bucket_index)190 void ReleaseBucket(int bucket_index) { 191 DeleteArray<uint32_t>(bucket[bucket_index]); 192 bucket[bucket_index] = nullptr; 193 } 194 MaskCell(int bucket_index,int cell_index,uint32_t mask)195 void MaskCell(int bucket_index, int cell_index, uint32_t mask) { 196 uint32_t* cells = bucket[bucket_index]; 197 if (cells != nullptr && cells[cell_index] != 0) { 198 cells[cell_index] &= mask; 199 } 200 } 201 202 // Converts the slot offset into bucket/cell/bit index. SlotToIndices(int slot_offset,int * bucket_index,int * cell_index,int * bit_index)203 void SlotToIndices(int slot_offset, int* bucket_index, int* cell_index, 204 int* bit_index) { 205 DCHECK_EQ(slot_offset % kPointerSize, 0); 206 int slot = slot_offset >> kPointerSizeLog2; 207 DCHECK(slot >= 0 && slot <= kMaxSlots); 208 *bucket_index = slot >> kBitsPerBucketLog2; 209 *cell_index = (slot >> kBitsPerCellLog2) & (kCellsPerBucket - 1); 210 *bit_index = slot & (kBitsPerCell - 1); 211 } 212 213 uint32_t* bucket[kBuckets]; 214 Address page_start_; 215 }; 216 217 enum SlotType { 218 EMBEDDED_OBJECT_SLOT, 219 OBJECT_SLOT, 220 CELL_TARGET_SLOT, 221 CODE_TARGET_SLOT, 222 CODE_ENTRY_SLOT, 223 DEBUG_TARGET_SLOT, 224 NUMBER_OF_SLOT_TYPES 225 }; 226 227 // Data structure for maintaining a multiset of typed slots in a page. 228 // Typed slots can only appear in Code and JSFunction objects, so 229 // the maximum possible offset is limited by the LargePage::kMaxCodePageSize. 230 // The implementation is a chain of chunks, where each chunks is an array of 231 // encoded (slot type, slot offset) pairs. 232 // There is no duplicate detection and we do not expect many duplicates because 233 // typed slots contain V8 internal pointers that are not directly exposed to JS. 234 class TypedSlotSet { 235 public: 236 struct TypedSlot { TypedSlotTypedSlot237 TypedSlot() : type_and_offset_(0), host_offset_(0) {} 238 TypedSlotTypedSlot239 TypedSlot(SlotType type, uint32_t host_offset, uint32_t offset) 240 : type_and_offset_(TypeField::encode(type) | 241 OffsetField::encode(offset)), 242 host_offset_(host_offset) {} 243 244 bool operator==(const TypedSlot other) { 245 return type_and_offset_ == other.type_and_offset_ && 246 host_offset_ == other.host_offset_; 247 } 248 249 bool operator!=(const TypedSlot other) { return !(*this == other); } 250 typeTypedSlot251 SlotType type() { return TypeField::decode(type_and_offset_); } 252 offsetTypedSlot253 uint32_t offset() { return OffsetField::decode(type_and_offset_); } 254 host_offsetTypedSlot255 uint32_t host_offset() { return host_offset_; } 256 257 uint32_t type_and_offset_; 258 uint32_t host_offset_; 259 }; 260 static const int kMaxOffset = 1 << 29; 261 TypedSlotSet(Address page_start)262 explicit TypedSlotSet(Address page_start) : page_start_(page_start) { 263 chunk_ = new Chunk(nullptr, kInitialBufferSize); 264 } 265 ~TypedSlotSet()266 ~TypedSlotSet() { 267 Chunk* chunk = chunk_; 268 while (chunk != nullptr) { 269 Chunk* next = chunk->next; 270 delete chunk; 271 chunk = next; 272 } 273 } 274 275 // The slot offset specifies a slot at address page_start_ + offset. Insert(SlotType type,uint32_t host_offset,uint32_t offset)276 void Insert(SlotType type, uint32_t host_offset, uint32_t offset) { 277 TypedSlot slot(type, host_offset, offset); 278 if (!chunk_->AddSlot(slot)) { 279 chunk_ = new Chunk(chunk_, NextCapacity(chunk_->capacity)); 280 bool added = chunk_->AddSlot(slot); 281 DCHECK(added); 282 USE(added); 283 } 284 } 285 286 // Iterate over all slots in the set and for each slot invoke the callback. 287 // If the callback returns REMOVE_SLOT then the slot is removed from the set. 288 // Returns the new number of slots. 289 // 290 // Sample usage: 291 // Iterate([](SlotType slot_type, Address slot_address) { 292 // if (good(slot_type, slot_address)) return KEEP_SLOT; 293 // else return REMOVE_SLOT; 294 // }); 295 template <typename Callback> Iterate(Callback callback)296 int Iterate(Callback callback) { 297 STATIC_ASSERT(NUMBER_OF_SLOT_TYPES < 8); 298 const TypedSlot kRemovedSlot(NUMBER_OF_SLOT_TYPES, 0, 0); 299 Chunk* chunk = chunk_; 300 int new_count = 0; 301 while (chunk != nullptr) { 302 TypedSlot* buffer = chunk->buffer; 303 int count = chunk->count; 304 for (int i = 0; i < count; i++) { 305 TypedSlot slot = buffer[i]; 306 if (slot != kRemovedSlot) { 307 SlotType type = slot.type(); 308 Address addr = page_start_ + slot.offset(); 309 Address host_addr = page_start_ + slot.host_offset(); 310 if (callback(type, host_addr, addr) == KEEP_SLOT) { 311 new_count++; 312 } else { 313 buffer[i] = kRemovedSlot; 314 } 315 } 316 } 317 chunk = chunk->next; 318 } 319 return new_count; 320 } 321 322 private: 323 static const int kInitialBufferSize = 100; 324 static const int kMaxBufferSize = 16 * KB; 325 NextCapacity(int capacity)326 static int NextCapacity(int capacity) { 327 return Min(kMaxBufferSize, capacity * 2); 328 } 329 330 class OffsetField : public BitField<int, 0, 29> {}; 331 class TypeField : public BitField<SlotType, 29, 3> {}; 332 333 struct Chunk : Malloced { ChunkChunk334 explicit Chunk(Chunk* next_chunk, int capacity) 335 : next(next_chunk), count(0), capacity(capacity) { 336 buffer = NewArray<TypedSlot>(capacity); 337 } AddSlotChunk338 bool AddSlot(TypedSlot slot) { 339 if (count == capacity) return false; 340 buffer[count++] = slot; 341 return true; 342 } ~ChunkChunk343 ~Chunk() { DeleteArray(buffer); } 344 Chunk* next; 345 int count; 346 int capacity; 347 TypedSlot* buffer; 348 }; 349 350 Address page_start_; 351 Chunk* chunk_; 352 }; 353 354 } // namespace internal 355 } // namespace v8 356 357 #endif // V8_SLOT_SET_H 358