OLD | NEW |
1 // Copyright 2016 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_SLOT_SET_H | 5 #ifndef V8_SLOT_SET_H |
6 #define V8_SLOT_SET_H | 6 #define V8_SLOT_SET_H |
7 | 7 |
8 #include "src/allocation.h" | 8 #include "src/allocation.h" |
9 #include "src/base/bits.h" | 9 #include "src/base/bits.h" |
| 10 #include "src/utils.h" |
10 | 11 |
11 namespace v8 { | 12 namespace v8 { |
12 namespace internal { | 13 namespace internal { |
13 | 14 |
| 15 enum SlotCallbackResult { KEEP_SLOT, REMOVE_SLOT }; |
| 16 |
14 // Data structure for maintaining a set of slots in a standard (non-large) | 17 // Data structure for maintaining a set of slots in a standard (non-large) |
15 // page. The base address of the page must be set with SetPageStart before any | 18 // page. The base address of the page must be set with SetPageStart before any |
16 // operation. | 19 // operation. |
17 // The data structure assumes that the slots are pointer size aligned and | 20 // The data structure assumes that the slots are pointer size aligned and |
18 // splits the valid slot offset range into kBuckets buckets. | 21 // splits the valid slot offset range into kBuckets buckets. |
19 // Each bucket is a bitmap with a bit corresponding to a single slot offset. | 22 // Each bucket is a bitmap with a bit corresponding to a single slot offset. |
20 class SlotSet : public Malloced { | 23 class SlotSet : public Malloced { |
21 public: | 24 public: |
22 enum CallbackResult { KEEP_SLOT, REMOVE_SLOT }; | |
23 | |
24 SlotSet() { | 25 SlotSet() { |
25 for (int i = 0; i < kBuckets; i++) { | 26 for (int i = 0; i < kBuckets; i++) { |
26 bucket[i] = nullptr; | 27 bucket[i] = nullptr; |
27 } | 28 } |
28 } | 29 } |
29 | 30 |
30 ~SlotSet() { | 31 ~SlotSet() { |
31 for (int i = 0; i < kBuckets; i++) { | 32 for (int i = 0; i < kBuckets; i++) { |
32 ReleaseBucket(i); | 33 ReleaseBucket(i); |
33 } | 34 } |
(...skipping 172 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
206 DCHECK(slot >= 0 && slot <= kMaxSlots); | 207 DCHECK(slot >= 0 && slot <= kMaxSlots); |
207 *bucket_index = slot >> kBitsPerBucketLog2; | 208 *bucket_index = slot >> kBitsPerBucketLog2; |
208 *cell_index = (slot >> kBitsPerCellLog2) & (kCellsPerBucket - 1); | 209 *cell_index = (slot >> kBitsPerCellLog2) & (kCellsPerBucket - 1); |
209 *bit_index = slot & (kBitsPerCell - 1); | 210 *bit_index = slot & (kBitsPerCell - 1); |
210 } | 211 } |
211 | 212 |
212 uint32_t* bucket[kBuckets]; | 213 uint32_t* bucket[kBuckets]; |
213 Address page_start_; | 214 Address page_start_; |
214 }; | 215 }; |
215 | 216 |
| 217 enum SlotType { |
| 218 EMBEDDED_OBJECT_SLOT, |
| 219 OBJECT_SLOT, |
| 220 RELOCATED_CODE_OBJECT, |
| 221 CELL_TARGET_SLOT, |
| 222 CODE_TARGET_SLOT, |
| 223 CODE_ENTRY_SLOT, |
| 224 DEBUG_TARGET_SLOT, |
| 225 NUMBER_OF_SLOT_TYPES |
| 226 }; |
| 227 |
| 228 // Data structure for maintaining a multiset of typed slots in a page. |
| 229 // Typed slots can only appear in Code and JSFunction objects, so |
| 230 // the maximum possible offset is limited by the LargePage::kMaxCodePageSize. |
| 231 // The implementation is a chain of chunks, where each chunks is an array of |
| 232 // encoded (slot type, slot offset) pairs. |
| 233 // There is no duplicate detection and we do not expect many duplicates because |
| 234 // typed slots contain V8 internal pointers that are not directly exposed to JS. |
| 235 class TypedSlotSet { |
| 236 public: |
| 237 typedef uint32_t TypedSlot; |
| 238 static const int kMaxOffset = 1 << 29; |
| 239 |
| 240 explicit TypedSlotSet(Address page_start) : page_start_(page_start) { |
| 241 chunk_ = new Chunk(nullptr, kInitialBufferSize); |
| 242 } |
| 243 |
| 244 ~TypedSlotSet() { |
| 245 Chunk* chunk = chunk_; |
| 246 while (chunk != nullptr) { |
| 247 Chunk* next = chunk->next; |
| 248 delete chunk; |
| 249 chunk = next; |
| 250 } |
| 251 } |
| 252 |
| 253 // The slot offset specifies a slot at address page_start_ + offset. |
| 254 void Insert(SlotType type, int offset) { |
| 255 TypedSlot slot = ToTypedSlot(type, offset); |
| 256 if (!chunk_->AddSlot(slot)) { |
| 257 chunk_ = new Chunk(chunk_, NextCapacity(chunk_->capacity)); |
| 258 bool added = chunk_->AddSlot(slot); |
| 259 DCHECK(added); |
| 260 USE(added); |
| 261 } |
| 262 } |
| 263 |
| 264 // Iterate over all slots in the set and for each slot invoke the callback. |
| 265 // If the callback returns REMOVE_SLOT then the slot is removed from the set. |
| 266 // Returns the new number of slots. |
| 267 // |
| 268 // Sample usage: |
| 269 // Iterate([](SlotType slot_type, Address slot_address) { |
| 270 // if (good(slot_type, slot_address)) return KEEP_SLOT; |
| 271 // else return REMOVE_SLOT; |
| 272 // }); |
| 273 template <typename Callback> |
| 274 int Iterate(Callback callback) { |
| 275 STATIC_ASSERT(NUMBER_OF_SLOT_TYPES < 8); |
| 276 const TypedSlot kRemovedSlot = TypeField::encode(NUMBER_OF_SLOT_TYPES); |
| 277 Chunk* chunk = chunk_; |
| 278 int new_count = 0; |
| 279 while (chunk != nullptr) { |
| 280 TypedSlot* buffer = chunk->buffer; |
| 281 int count = chunk->count; |
| 282 for (int i = 0; i < count; i++) { |
| 283 TypedSlot slot = buffer[i]; |
| 284 if (slot != kRemovedSlot) { |
| 285 SlotType type = TypeField::decode(slot); |
| 286 Address addr = page_start_ + OffsetField::decode(slot); |
| 287 if (callback(type, addr) == KEEP_SLOT) { |
| 288 new_count++; |
| 289 } else { |
| 290 buffer[i] = kRemovedSlot; |
| 291 } |
| 292 } |
| 293 } |
| 294 chunk = chunk->next; |
| 295 } |
| 296 return new_count; |
| 297 } |
| 298 |
| 299 private: |
| 300 static const int kInitialBufferSize = 100; |
| 301 static const int kMaxBufferSize = 16 * KB; |
| 302 |
| 303 static int NextCapacity(int capacity) { |
| 304 return Min(kMaxBufferSize, capacity * 2); |
| 305 } |
| 306 |
| 307 static TypedSlot ToTypedSlot(SlotType type, int offset) { |
| 308 return TypeField::encode(type) | OffsetField::encode(offset); |
| 309 } |
| 310 |
| 311 class OffsetField : public BitField<int, 0, 29> {}; |
| 312 class TypeField : public BitField<SlotType, 29, 3> {}; |
| 313 |
| 314 struct Chunk : Malloced { |
| 315 explicit Chunk(Chunk* next_chunk, int capacity) |
| 316 : next(next_chunk), count(0), capacity(capacity) { |
| 317 buffer = NewArray<TypedSlot>(capacity); |
| 318 } |
| 319 bool AddSlot(TypedSlot slot) { |
| 320 if (count == capacity) return false; |
| 321 buffer[count++] = slot; |
| 322 return true; |
| 323 } |
| 324 ~Chunk() { DeleteArray(buffer); } |
| 325 Chunk* next; |
| 326 int count; |
| 327 int capacity; |
| 328 TypedSlot* buffer; |
| 329 }; |
| 330 |
| 331 Address page_start_; |
| 332 Chunk* chunk_; |
| 333 }; |
| 334 |
216 } // namespace internal | 335 } // namespace internal |
217 } // namespace v8 | 336 } // namespace v8 |
218 | 337 |
219 #endif // V8_SLOT_SET_H | 338 #endif // V8_SLOT_SET_H |
OLD | NEW |