[heap] Reland Concurrently free empty typed slot set chunks.

src/heap/slot-set.h

 // Copyright 2016 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_SLOT_SET_H
 #define V8_SLOT_SET_H
 
+#include <stack>
+
 #include "src/allocation.h"
 #include "src/base/atomic-utils.h"
 #include "src/base/bits.h"
 #include "src/utils.h"
 
 namespace v8 {
 namespace internal {
 
 enum SlotCallbackResult { KEEP_SLOT, REMOVE_SLOT };
 
@@ skipping 234 matching lines @@
 
 // Data structure for maintaining a multiset of typed slots in a page.
 // Typed slots can only appear in Code and JSFunction objects, so
 // the maximum possible offset is limited by the LargePage::kMaxCodePageSize.
 // The implementation is a chain of chunks, where each chunks is an array of
 // encoded (slot type, slot offset) pairs.
 // There is no duplicate detection and we do not expect many duplicates because
 // typed slots contain V8 internal pointers that are not directly exposed to JS.
 class TypedSlotSet {
  public:
+  enum IterationMode { PREFREE_EMPTY_CHUNKS, KEEP_EMPTY_CHUNKS };
+
   typedef std::pair<SlotType, uint32_t> TypeAndOffset;
 
   struct TypedSlot {
     TypedSlot() {
       type_and_offset_.SetValue(0);
       host_offset_.SetValue(0);
     }
 
     TypedSlot(SlotType type, uint32_t host_offset, uint32_t offset) {
       type_and_offset_.SetValue(TypeField::encode(type) |
@@ skipping 47 matching lines @@
       delete chunk;
       chunk = next;
     }
   }
 
   // The slot offset specifies a slot at address page_start_ + offset.
   // This method can only be called on the main thread.
   void Insert(SlotType type, uint32_t host_offset, uint32_t offset) {
     TypedSlot slot(type, host_offset, offset);
     Chunk* top_chunk = chunk_.Value();
+    if (!top_chunk) {
+      top_chunk = new Chunk(nullptr, kInitialBufferSize);
+      chunk_.SetValue(top_chunk);
+    }
     if (!top_chunk->AddSlot(slot)) {
       Chunk* new_top_chunk =
           new Chunk(top_chunk, NextCapacity(top_chunk->capacity.Value()));
       bool added = new_top_chunk->AddSlot(slot);
       chunk_.SetValue(new_top_chunk);
       DCHECK(added);
       USE(added);
     }
   }
 
   // Iterate over all slots in the set and for each slot invoke the callback.
   // If the callback returns REMOVE_SLOT then the slot is removed from the set.
   // Returns the new number of slots.
   //
   // Sample usage:
   // Iterate([](SlotType slot_type, Address slot_address) {
   //    if (good(slot_type, slot_address)) return KEEP_SLOT;
   //    else return REMOVE_SLOT;
   // });
   template <typename Callback>
-  int Iterate(Callback callback) {
+  int Iterate(Callback callback, IterationMode mode) {
     STATIC_ASSERT(CLEARED_SLOT < 8);
     Chunk* chunk = chunk_.Value();
+    Chunk* previous = nullptr;
     int new_count = 0;
     while (chunk != nullptr) {
       TypedSlot* buffer = chunk->buffer.Value();
       int count = chunk->count.Value();
+      bool empty = true;
       for (int i = 0; i < count; i++) {
         // Order is important here. We have to read out the slot type last to
         // observe the concurrent removal case consistently.
         Address host_addr = page_start_ + buffer[i].host_offset();
         TypeAndOffset type_and_offset = buffer[i].GetTypeAndOffset();
         SlotType type = type_and_offset.first;
         if (type != CLEARED_SLOT) {
           Address addr = page_start_ + type_and_offset.second;
           if (callback(type, host_addr, addr) == KEEP_SLOT) {
             new_count++;
+            empty = false;
           } else {
             buffer[i].Clear();
           }
         }
       }
+
+      if (mode == PREFREE_EMPTY_CHUNKS && empty) {
+        // We remove the chunk from the list but let it still point its next
+        // chunk to allow concurrent iteration.
+        if (previous) {
+          previous->next.SetValue(chunk->next.Value());
+        } else {
+          chunk_.SetValue(chunk->next.Value());
+        }
+        base::LockGuard<base::Mutex> guard(&to_be_freed_chunks_mutex_);
+        to_be_freed_chunks_.push(chunk);
+      } else {
+        previous = chunk;
+      }
       chunk = chunk->next.Value();
     }
     return new_count;
   }
 
+  void FreeToBeFreedChunks() {
+    base::LockGuard<base::Mutex> guard(&to_be_freed_chunks_mutex_);
+    while (!to_be_freed_chunks_.empty()) {
+      Chunk* top = to_be_freed_chunks_.top();
+      to_be_freed_chunks_.pop();
+      delete top;
+    }
+  }
+
  private:
   static const int kInitialBufferSize = 100;
   static const int kMaxBufferSize = 16 * KB;
 
   static int NextCapacity(int capacity) {
     return Min(kMaxBufferSize, capacity * 2);
   }
 
   class OffsetField : public BitField<int, 0, 29> {};
   class TypeField : public BitField<SlotType, 29, 3> {};
@@ skipping 18 matching lines @@
     }
     ~Chunk() { DeleteArray(buffer.Value()); }
     base::AtomicValue<Chunk*> next;
     base::AtomicValue<int> count;
     base::AtomicValue<int> capacity;
     base::AtomicValue<TypedSlot*> buffer;
   };
 
   Address page_start_;
   base::AtomicValue<Chunk*> chunk_;
+  base::Mutex to_be_freed_chunks_mutex_;
+  std::stack<Chunk*> to_be_freed_chunks_;
 };
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_SLOT_SET_H