[heap] Concurrently free empty slot set buckets.

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 };
 
 // Data structure for maintaining a set of slots in a standard (non-large)
 // page. The base address of the page must be set with SetPageStart before any
 // operation.
 // The data structure assumes that the slots are pointer size aligned and
 // splits the valid slot offset range into kBuckets buckets.
 // Each bucket is a bitmap with a bit corresponding to a single slot offset.
 class SlotSet : public Malloced {
  public:
+  enum IterationMode { PREFREE_EMPTY_BUCKETS, KEEP_EMPTY_BUCKETS };

[Hannes Payer (out of office), 2016/10/05 08:59:30]

KEEP_EMPTY_BUCKETS will be used as soon as we move filtering to the sweeper.

+
   SlotSet() {
     for (int i = 0; i < kBuckets; i++) {
       bucket[i].SetValue(nullptr);
     }
   }
 
   ~SlotSet() {
     for (int i = 0; i < kBuckets; i++) {
       ReleaseBucket(i);
     }
+    FreeToBeFreedBuckets();
   }
 
   void SetPageStart(Address page_start) { page_start_ = page_start; }
 
   // The slot offset specifies a slot at address page_start_ + slot_offset.
   // This method should only be called on the main thread because concurrent
   // allocation of the bucket is not thread-safe.
   void Insert(int slot_offset) {
     int bucket_index, cell_index, bit_index;
     SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index);
@@ skipping 90 matching lines @@
   // If the callback returns REMOVE_SLOT then the slot is removed from the set.
   // Returns the new number of slots.
   // This method should only be called on the main thread.
   //
   // Sample usage:
   // Iterate([](Address slot_address) {
   //    if (good(slot_address)) return KEEP_SLOT;
   //    else return REMOVE_SLOT;
   // });
   template <typename Callback>
-  int Iterate(Callback callback) {
+  int Iterate(Callback callback, IterationMode mode) {
     int new_count = 0;
     for (int bucket_index = 0; bucket_index < kBuckets; bucket_index++) {
       if (bucket[bucket_index].Value() != nullptr) {
         int in_bucket_count = 0;
         base::AtomicValue<uint32_t>* current_bucket =
             bucket[bucket_index].Value();
         int cell_offset = bucket_index * kBitsPerBucket;
         for (int i = 0; i < kCellsPerBucket; i++, cell_offset += kBitsPerCell) {
           if (current_bucket[i].Value()) {
             uint32_t cell = current_bucket[i].Value();
@@ skipping 16 matching lines @@
                 // have to read the current value of the cell, & it with the
                 // computed value, and retry. We can do this, because this
                 // method will only be called on the main thread and filtering
                 // threads will only remove slots.
                 old_cell = current_bucket[i].Value();
                 new_cell &= old_cell;
               }
             }
           }
         }
-        if (in_bucket_count == 0) {
-          ReleaseBucket(bucket_index);
+        if (mode == PREFREE_EMPTY_BUCKETS && in_bucket_count == 0) {
+          base::LockGuard<base::Mutex> guard(&to_be_freed_buckets_mutex_);
+          base::AtomicValue<uint32_t>* bucket_ptr =
+              bucket[bucket_index].Value();
+          to_be_freed_buckets_.push(bucket_ptr);
+          bucket[bucket_index].SetValue(nullptr);
         }
         new_count += in_bucket_count;
       }
     }
     return new_count;
   }
 
+  void FreeToBeFreedBuckets() {
+    base::LockGuard<base::Mutex> guard(&to_be_freed_buckets_mutex_);
+    while (!to_be_freed_buckets_.empty()) {
+      base::AtomicValue<uint32_t>* top = to_be_freed_buckets_.top();
+      to_be_freed_buckets_.pop();
+      DeleteArray<base::AtomicValue<uint32_t>>(top);
+    }
+  }
+
  private:
   static const int kMaxSlots = (1 << kPageSizeBits) / kPointerSize;
   static const int kCellsPerBucket = 32;
   static const int kCellsPerBucketLog2 = 5;
   static const int kBitsPerCell = 32;
   static const int kBitsPerCellLog2 = 5;
   static const int kBitsPerBucket = kCellsPerBucket * kBitsPerCell;
   static const int kBitsPerBucketLog2 = kCellsPerBucketLog2 + kBitsPerCellLog2;
   static const int kBuckets = kMaxSlots / kCellsPerBucket / kBitsPerCell;
 
@@ skipping 31 matching lines @@
     DCHECK_EQ(slot_offset % kPointerSize, 0);
     int slot = slot_offset >> kPointerSizeLog2;
     DCHECK(slot >= 0 && slot <= kMaxSlots);
     *bucket_index = slot >> kBitsPerBucketLog2;
     *cell_index = (slot >> kBitsPerCellLog2) & (kCellsPerBucket - 1);
     *bit_index = slot & (kBitsPerCell - 1);
   }
 
   base::AtomicValue<base::AtomicValue<uint32_t>*> bucket[kBuckets];
   Address page_start_;
+  base::Mutex to_be_freed_buckets_mutex_;
+  std::stack<base::AtomicValue<uint32_t>*> to_be_freed_buckets_;
 };
 
 enum SlotType {
   EMBEDDED_OBJECT_SLOT,
   OBJECT_SLOT,
   CELL_TARGET_SLOT,
   CODE_TARGET_SLOT,
   CODE_ENTRY_SLOT,
   DEBUG_TARGET_SLOT,
   CLEARED_SLOT
@@ skipping 194 matching lines @@
   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