[heap] Make typed slot set state and operations atomic.

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 "src/allocation.h"
 #include "src/base/atomic-utils.h"
 #include "src/base/bits.h"
@@ skipping 229 matching lines @@
   Address page_start_;
 };
 
 enum SlotType {
   EMBEDDED_OBJECT_SLOT,
   OBJECT_SLOT,
   CELL_TARGET_SLOT,
   CODE_TARGET_SLOT,
   CODE_ENTRY_SLOT,
   DEBUG_TARGET_SLOT,
-  NUMBER_OF_SLOT_TYPES
+  NUMBER_OF_SLOT_TYPES,
+  CLEARED_SLOT = NUMBER_OF_SLOT_TYPES,
 };
 
 // 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:
   struct TypedSlot {
-    TypedSlot() : type_and_offset_(0), host_offset_(0) {}
+    TypedSlot() {
+      type_and_offset_.SetValue(0);
+      host_offset_.SetValue(0);
+    }
 
-    TypedSlot(SlotType type, uint32_t host_offset, uint32_t offset)
-        : type_and_offset_(TypeField::encode(type) |
-                           OffsetField::encode(offset)),
-          host_offset_(host_offset) {}
+    TypedSlot(SlotType type, uint32_t host_offset, uint32_t offset) {
+      type_and_offset_.SetValue(TypeField::encode(type) |
+                                OffsetField::encode(offset));
+      host_offset_.SetValue(host_offset);
+    }
 
     bool operator==(const TypedSlot other) {
-      return type_and_offset_ == other.type_and_offset_ &&
-             host_offset_ == other.host_offset_;
+      return type_and_offset_.Value() == other.type_and_offset_.Value() &&
+             host_offset_.Value() == other.host_offset_.Value();
     }
 
     bool operator!=(const TypedSlot other) { return !(*this == other); }
 
-    SlotType type() { return TypeField::decode(type_and_offset_); }
+    SlotType type() { return TypeField::decode(type_and_offset_.Value()); }
 
-    uint32_t offset() { return OffsetField::decode(type_and_offset_); }
+    uint32_t offset() { return OffsetField::decode(type_and_offset_.Value()); }
 
-    uint32_t host_offset() { return host_offset_; }
+    uint32_t host_offset() { return host_offset_.Value(); }
 
-    uint32_t type_and_offset_;
-    uint32_t host_offset_;
+    void Set(TypedSlot slot) {
+      type_and_offset_.SetValue(slot.type_and_offset_.Value());
+      host_offset_.SetValue(slot.host_offset_.Value());
+    }
+
+    void Clear() {
+      type_and_offset_.SetValue(TypeField::encode(CLEARED_SLOT) |
+                                OffsetField::encode(0));
+      host_offset_.SetValue(0);
+    }
+
+    base::AtomicValue<uint32_t> type_and_offset_;
+    base::AtomicValue<uint32_t> host_offset_;
   };
   static const int kMaxOffset = 1 << 29;
 
   explicit TypedSlotSet(Address page_start) : page_start_(page_start) {
-    chunk_ = new Chunk(nullptr, kInitialBufferSize);
+    chunk_.SetValue(new Chunk(nullptr, kInitialBufferSize));
   }
 
   ~TypedSlotSet() {
-    Chunk* chunk = chunk_;
+    Chunk* chunk = chunk_.Value();
     while (chunk != nullptr) {
-      Chunk* next = chunk->next;
+      Chunk* next = chunk->next.Value();
       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);
-    if (!chunk_->AddSlot(slot)) {
-      chunk_ = new Chunk(chunk_, NextCapacity(chunk_->capacity));
-      bool added = chunk_->AddSlot(slot);
+    Chunk* top_chunk = chunk_.Value();
+    if (!top_chunk->AddSlot(slot)) {
+      Chunk* new_top_chunk =
+          new Chunk(top_chunk, NextCapacity(top_chunk->capacity.Value()));
+      chunk_.SetValue(new_top_chunk);
+      bool added = new_top_chunk->AddSlot(slot);

[ulan, 2016/09/21 11:52:35]

Nit: how about swapping the order of these two operations: add slot and then set
the chunk_?

[Hannes Payer (out of office), 2016/09/21 12:14:15]

Done.

       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) {
     STATIC_ASSERT(NUMBER_OF_SLOT_TYPES < 8);
-    const TypedSlot kRemovedSlot(NUMBER_OF_SLOT_TYPES, 0, 0);
-    Chunk* chunk = chunk_;
+    Chunk* chunk = chunk_.Value();
     int new_count = 0;
     while (chunk != nullptr) {
-      TypedSlot* buffer = chunk->buffer;
-      int count = chunk->count;
+      TypedSlot* buffer = chunk->buffer.Value();
+      int count = chunk->count.Value();
       for (int i = 0; i < count; i++) {
-        TypedSlot slot = buffer[i];
-        if (slot != kRemovedSlot) {
-          SlotType type = slot.type();
-          Address addr = page_start_ + slot.offset();
-          Address host_addr = page_start_ + slot.host_offset();
+        SlotType type = buffer[i].type();
+        if (type != CLEARED_SLOT) {
+          Address addr = page_start_ + buffer[i].offset();
+          Address host_addr = page_start_ + buffer[i].host_offset();

[ulan, 2016/09/21 11:52:35]

As discussed offline, we need to change order of loads here.

[Hannes Payer (out of office), 2016/09/21 12:14:15]

Done.

We could also change it to only read out the word with the type once. However,
that would lift the low level representation to that method, which is not nice.

           if (callback(type, host_addr, addr) == KEEP_SLOT) {
             new_count++;
           } else {
-            buffer[i] = kRemovedSlot;
+            buffer[i].Clear();
           }
         }
       }
-      chunk = chunk->next;
+      chunk = chunk->next.Value();
     }
     return new_count;
   }
 
  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> {};
 
   struct Chunk : Malloced {
-    explicit Chunk(Chunk* next_chunk, int capacity)
-        : next(next_chunk), count(0), capacity(capacity) {
-      buffer = NewArray<TypedSlot>(capacity);
+    explicit Chunk(Chunk* next_chunk, int chunk_capacity) {
+      count.SetValue(0);
+      capacity.SetValue(chunk_capacity);
+      buffer.SetValue(NewArray<TypedSlot>(chunk_capacity));
+      next.SetValue(next_chunk);
     }
     bool AddSlot(TypedSlot slot) {
-      if (count == capacity) return false;
-      buffer[count++] = slot;
+      int current_count = count.Value();
+      if (current_count == capacity.Value()) return false;
+      TypedSlot* current_buffer = buffer.Value();
+      // Order is important here. We have to write the slot first before
+      // increasing the counter to guarantee that a consistent state is
+      // observed by concurrent threads.
+      current_buffer[current_count].Set(slot);
+      count.SetValue(current_count + 1);
       return true;
     }
-    ~Chunk() { DeleteArray(buffer); }
-    Chunk* next;
-    int count;
-    int capacity;
-    TypedSlot* buffer;
+    ~Chunk() { DeleteArray(buffer.Value()); }
+    base::AtomicValue<Chunk*> next;
+    base::AtomicValue<int> count;
+    base::AtomicValue<int> capacity;
+    base::AtomicValue<TypedSlot*> buffer;
   };
 
   Address page_start_;
-  Chunk* chunk_;
+  base::AtomicValue<Chunk*> chunk_;
 };
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_SLOT_SET_H