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 <stack> |
| 9 |
8 #include "src/allocation.h" | 10 #include "src/allocation.h" |
9 #include "src/base/atomic-utils.h" | 11 #include "src/base/atomic-utils.h" |
10 #include "src/base/bits.h" | 12 #include "src/base/bits.h" |
11 #include "src/utils.h" | 13 #include "src/utils.h" |
12 | 14 |
13 namespace v8 { | 15 namespace v8 { |
14 namespace internal { | 16 namespace internal { |
15 | 17 |
16 enum SlotCallbackResult { KEEP_SLOT, REMOVE_SLOT }; | 18 enum SlotCallbackResult { KEEP_SLOT, REMOVE_SLOT }; |
17 | 19 |
(...skipping 234 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
252 | 254 |
253 // Data structure for maintaining a multiset of typed slots in a page. | 255 // Data structure for maintaining a multiset of typed slots in a page. |
254 // Typed slots can only appear in Code and JSFunction objects, so | 256 // Typed slots can only appear in Code and JSFunction objects, so |
255 // the maximum possible offset is limited by the LargePage::kMaxCodePageSize. | 257 // the maximum possible offset is limited by the LargePage::kMaxCodePageSize. |
256 // The implementation is a chain of chunks, where each chunks is an array of | 258 // The implementation is a chain of chunks, where each chunks is an array of |
257 // encoded (slot type, slot offset) pairs. | 259 // encoded (slot type, slot offset) pairs. |
258 // There is no duplicate detection and we do not expect many duplicates because | 260 // There is no duplicate detection and we do not expect many duplicates because |
259 // typed slots contain V8 internal pointers that are not directly exposed to JS. | 261 // typed slots contain V8 internal pointers that are not directly exposed to JS. |
260 class TypedSlotSet { | 262 class TypedSlotSet { |
261 public: | 263 public: |
| 264 enum IterationMode { PREFREE_EMPTY_CHUNKS, KEEP_EMPTY_CHUNKS }; |
| 265 |
262 typedef std::pair<SlotType, uint32_t> TypeAndOffset; | 266 typedef std::pair<SlotType, uint32_t> TypeAndOffset; |
263 | 267 |
264 struct TypedSlot { | 268 struct TypedSlot { |
265 TypedSlot() { | 269 TypedSlot() { |
266 type_and_offset_.SetValue(0); | 270 type_and_offset_.SetValue(0); |
267 host_offset_.SetValue(0); | 271 host_offset_.SetValue(0); |
268 } | 272 } |
269 | 273 |
270 TypedSlot(SlotType type, uint32_t host_offset, uint32_t offset) { | 274 TypedSlot(SlotType type, uint32_t host_offset, uint32_t offset) { |
271 type_and_offset_.SetValue(TypeField::encode(type) | | 275 type_and_offset_.SetValue(TypeField::encode(type) | |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
319 delete chunk; | 323 delete chunk; |
320 chunk = next; | 324 chunk = next; |
321 } | 325 } |
322 } | 326 } |
323 | 327 |
324 // The slot offset specifies a slot at address page_start_ + offset. | 328 // The slot offset specifies a slot at address page_start_ + offset. |
325 // This method can only be called on the main thread. | 329 // This method can only be called on the main thread. |
326 void Insert(SlotType type, uint32_t host_offset, uint32_t offset) { | 330 void Insert(SlotType type, uint32_t host_offset, uint32_t offset) { |
327 TypedSlot slot(type, host_offset, offset); | 331 TypedSlot slot(type, host_offset, offset); |
328 Chunk* top_chunk = chunk_.Value(); | 332 Chunk* top_chunk = chunk_.Value(); |
| 333 if (!top_chunk) { |
| 334 top_chunk = new Chunk(nullptr, kInitialBufferSize); |
| 335 chunk_.SetValue(top_chunk); |
| 336 } |
329 if (!top_chunk->AddSlot(slot)) { | 337 if (!top_chunk->AddSlot(slot)) { |
330 Chunk* new_top_chunk = | 338 Chunk* new_top_chunk = |
331 new Chunk(top_chunk, NextCapacity(top_chunk->capacity.Value())); | 339 new Chunk(top_chunk, NextCapacity(top_chunk->capacity.Value())); |
332 bool added = new_top_chunk->AddSlot(slot); | 340 bool added = new_top_chunk->AddSlot(slot); |
333 chunk_.SetValue(new_top_chunk); | 341 chunk_.SetValue(new_top_chunk); |
334 DCHECK(added); | 342 DCHECK(added); |
335 USE(added); | 343 USE(added); |
336 } | 344 } |
337 } | 345 } |
338 | 346 |
339 // Iterate over all slots in the set and for each slot invoke the callback. | 347 // Iterate over all slots in the set and for each slot invoke the callback. |
340 // If the callback returns REMOVE_SLOT then the slot is removed from the set. | 348 // If the callback returns REMOVE_SLOT then the slot is removed from the set. |
341 // Returns the new number of slots. | 349 // Returns the new number of slots. |
342 // | 350 // |
343 // Sample usage: | 351 // Sample usage: |
344 // Iterate([](SlotType slot_type, Address slot_address) { | 352 // Iterate([](SlotType slot_type, Address slot_address) { |
345 // if (good(slot_type, slot_address)) return KEEP_SLOT; | 353 // if (good(slot_type, slot_address)) return KEEP_SLOT; |
346 // else return REMOVE_SLOT; | 354 // else return REMOVE_SLOT; |
347 // }); | 355 // }); |
348 template <typename Callback> | 356 template <typename Callback> |
349 int Iterate(Callback callback) { | 357 int Iterate(Callback callback, IterationMode mode) { |
350 STATIC_ASSERT(CLEARED_SLOT < 8); | 358 STATIC_ASSERT(CLEARED_SLOT < 8); |
351 Chunk* chunk = chunk_.Value(); | 359 Chunk* chunk = chunk_.Value(); |
| 360 Chunk* previous = nullptr; |
352 int new_count = 0; | 361 int new_count = 0; |
353 while (chunk != nullptr) { | 362 while (chunk != nullptr) { |
354 TypedSlot* buffer = chunk->buffer.Value(); | 363 TypedSlot* buffer = chunk->buffer.Value(); |
355 int count = chunk->count.Value(); | 364 int count = chunk->count.Value(); |
| 365 bool empty = true; |
356 for (int i = 0; i < count; i++) { | 366 for (int i = 0; i < count; i++) { |
357 // Order is important here. We have to read out the slot type last to | 367 // Order is important here. We have to read out the slot type last to |
358 // observe the concurrent removal case consistently. | 368 // observe the concurrent removal case consistently. |
359 Address host_addr = page_start_ + buffer[i].host_offset(); | 369 Address host_addr = page_start_ + buffer[i].host_offset(); |
360 TypeAndOffset type_and_offset = buffer[i].GetTypeAndOffset(); | 370 TypeAndOffset type_and_offset = buffer[i].GetTypeAndOffset(); |
361 SlotType type = type_and_offset.first; | 371 SlotType type = type_and_offset.first; |
362 if (type != CLEARED_SLOT) { | 372 if (type != CLEARED_SLOT) { |
363 Address addr = page_start_ + type_and_offset.second; | 373 Address addr = page_start_ + type_and_offset.second; |
364 if (callback(type, host_addr, addr) == KEEP_SLOT) { | 374 if (callback(type, host_addr, addr) == KEEP_SLOT) { |
365 new_count++; | 375 new_count++; |
| 376 empty = false; |
366 } else { | 377 } else { |
367 buffer[i].Clear(); | 378 buffer[i].Clear(); |
368 } | 379 } |
369 } | 380 } |
370 } | 381 } |
| 382 |
| 383 if (mode == PREFREE_EMPTY_CHUNKS && empty) { |
| 384 // We remove the chunk from the list but let it still point its next |
| 385 // chunk to allow concurrent iteration. |
| 386 if (previous) { |
| 387 previous->next.SetValue(chunk->next.Value()); |
| 388 } else { |
| 389 chunk_.SetValue(chunk->next.Value()); |
| 390 } |
| 391 base::LockGuard<base::Mutex> guard(&to_be_freed_chunks_mutex_); |
| 392 to_be_freed_chunks_.push(chunk); |
| 393 } else { |
| 394 previous = chunk; |
| 395 } |
371 chunk = chunk->next.Value(); | 396 chunk = chunk->next.Value(); |
372 } | 397 } |
373 return new_count; | 398 return new_count; |
374 } | 399 } |
375 | 400 |
| 401 void FreeToBeFreedChunks() { |
| 402 base::LockGuard<base::Mutex> guard(&to_be_freed_chunks_mutex_); |
| 403 while (!to_be_freed_chunks_.empty()) { |
| 404 Chunk* top = to_be_freed_chunks_.top(); |
| 405 to_be_freed_chunks_.pop(); |
| 406 delete top; |
| 407 } |
| 408 } |
| 409 |
376 private: | 410 private: |
377 static const int kInitialBufferSize = 100; | 411 static const int kInitialBufferSize = 100; |
378 static const int kMaxBufferSize = 16 * KB; | 412 static const int kMaxBufferSize = 16 * KB; |
379 | 413 |
380 static int NextCapacity(int capacity) { | 414 static int NextCapacity(int capacity) { |
381 return Min(kMaxBufferSize, capacity * 2); | 415 return Min(kMaxBufferSize, capacity * 2); |
382 } | 416 } |
383 | 417 |
384 class OffsetField : public BitField<int, 0, 29> {}; | 418 class OffsetField : public BitField<int, 0, 29> {}; |
385 class TypeField : public BitField<SlotType, 29, 3> {}; | 419 class TypeField : public BitField<SlotType, 29, 3> {}; |
(...skipping 18 matching lines...) Expand all Loading... |
404 } | 438 } |
405 ~Chunk() { DeleteArray(buffer.Value()); } | 439 ~Chunk() { DeleteArray(buffer.Value()); } |
406 base::AtomicValue<Chunk*> next; | 440 base::AtomicValue<Chunk*> next; |
407 base::AtomicValue<int> count; | 441 base::AtomicValue<int> count; |
408 base::AtomicValue<int> capacity; | 442 base::AtomicValue<int> capacity; |
409 base::AtomicValue<TypedSlot*> buffer; | 443 base::AtomicValue<TypedSlot*> buffer; |
410 }; | 444 }; |
411 | 445 |
412 Address page_start_; | 446 Address page_start_; |
413 base::AtomicValue<Chunk*> chunk_; | 447 base::AtomicValue<Chunk*> chunk_; |
| 448 base::Mutex to_be_freed_chunks_mutex_; |
| 449 std::stack<Chunk*> to_be_freed_chunks_; |
414 }; | 450 }; |
415 | 451 |
416 } // namespace internal | 452 } // namespace internal |
417 } // namespace v8 | 453 } // namespace v8 |
418 | 454 |
419 #endif // V8_SLOT_SET_H | 455 #endif // V8_SLOT_SET_H |
OLD | NEW |