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