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" | |
11 | 10 |
12 namespace v8 { | 11 namespace v8 { |
13 namespace internal { | 12 namespace internal { |
14 | 13 |
15 enum SlotCallbackResult { KEEP_SLOT, REMOVE_SLOT }; | |
16 | |
17 // Data structure for maintaining a set of slots in a standard (non-large) | 14 // 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 | 15 // page. The base address of the page must be set with SetPageStart before any |
19 // operation. | 16 // operation. |
20 // The data structure assumes that the slots are pointer size aligned and | 17 // The data structure assumes that the slots are pointer size aligned and |
21 // splits the valid slot offset range into kBuckets buckets. | 18 // splits the valid slot offset range into kBuckets buckets. |
22 // Each bucket is a bitmap with a bit corresponding to a single slot offset. | 19 // Each bucket is a bitmap with a bit corresponding to a single slot offset. |
23 class SlotSet : public Malloced { | 20 class SlotSet : public Malloced { |
24 public: | 21 public: |
| 22 enum CallbackResult { KEEP_SLOT, REMOVE_SLOT }; |
| 23 |
25 SlotSet() { | 24 SlotSet() { |
26 for (int i = 0; i < kBuckets; i++) { | 25 for (int i = 0; i < kBuckets; i++) { |
27 bucket[i] = nullptr; | 26 bucket[i] = nullptr; |
28 } | 27 } |
29 } | 28 } |
30 | 29 |
31 ~SlotSet() { | 30 ~SlotSet() { |
32 for (int i = 0; i < kBuckets; i++) { | 31 for (int i = 0; i < kBuckets; i++) { |
33 ReleaseBucket(i); | 32 ReleaseBucket(i); |
34 } | 33 } |
(...skipping 172 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
207 DCHECK(slot >= 0 && slot <= kMaxSlots); | 206 DCHECK(slot >= 0 && slot <= kMaxSlots); |
208 *bucket_index = slot >> kBitsPerBucketLog2; | 207 *bucket_index = slot >> kBitsPerBucketLog2; |
209 *cell_index = (slot >> kBitsPerCellLog2) & (kCellsPerBucket - 1); | 208 *cell_index = (slot >> kBitsPerCellLog2) & (kCellsPerBucket - 1); |
210 *bit_index = slot & (kBitsPerCell - 1); | 209 *bit_index = slot & (kBitsPerCell - 1); |
211 } | 210 } |
212 | 211 |
213 uint32_t* bucket[kBuckets]; | 212 uint32_t* bucket[kBuckets]; |
214 Address page_start_; | 213 Address page_start_; |
215 }; | 214 }; |
216 | 215 |
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 | |
335 } // namespace internal | 216 } // namespace internal |
336 } // namespace v8 | 217 } // namespace v8 |
337 | 218 |
338 #endif // V8_SLOT_SET_H | 219 #endif // V8_SLOT_SET_H |
OLD | NEW |