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