New page local store buffer.

src/heap/slot-set.h

Index: src/heap/slot-set.h
diff --git a/src/heap/slot-set.h b/src/heap/slot-set.h
new file mode 100644
index 0000000000000000000000000000000000000000..2b7f6dd023c8049567e43f86848f878e11fddedc
--- /dev/null
+++ b/src/heap/slot-set.h
@@ -0,0 +1,214 @@
+// 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/base/bits.h"
+
+namespace v8 {
+namespace internal {
+
+
+// Data structure for maintaining a set of slots in a standard (non-large)

[Hannes Payer (out of office), 2016/01/20 19:43:00]

Why don't we also support large pages right away, i.e. allow a slot set of
arbitrary size? The constructor could take care of that.

[ulan, 2016/01/28 19:07:22]

The large page takes care of that by using an array of SlotSets.

I decided to not make SlotSet generic so that the common path (normal pages)
stay fast.

+// 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 {

[Michael Lippautz, 2016/01/21 10:07:32]

Make it inherit from public Malloced, so that we get proper V8 OOMs when
allocation using _new_ fails.

[ulan, 2016/01/28 19:07:22]

Done.

+ public:
+  SlotSet() {
+    for (int i = 0; i < kBuckets; i++) {
+      bucket[i] = nullptr;
+    }
+  }
+
+
+  ~SlotSet() {
+    for (int i = 0; i < kBuckets; i++) {
+      ReleaseBucket(i);
+    }
+  }
+
+
+  void SetPageStart(Address page_start) { page_start_ = page_start; }

[Hannes Payer (out of office), 2016/01/20 19:43:00]

If we allow arbitrary size slot sets, we would not need that method. As far as I
see, it is just needed to set up the large object case.

[ulan, 2016/01/28 19:07:22]

It is also used in the Iterate callback to convert slot offset to addresses.

+
+
+  // The slot offset specifies a slot at address page_start_ + slot_offset.
+  void Insert(int slot_offset) {
+    int bucket_index, cell_index, bit_index;
+    SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index);
+    if (bucket[bucket_index] == nullptr) {
+      bucket[bucket_index] = AllocateBucket();
+    }
+    bucket[bucket_index][cell_index] |= 1u << bit_index;

[Michael Lippautz, 2016/01/26 09:12:24]

Maybe we can additionally have a method {InsertSynchronized} that can be used
for parallel insertion? If we divide up memory upon compaction tasks, they may
end up using non-private pages, for which we would still require a local buffer.

The method would only need to handle concurrency with competing calls of
InsertSynchronized.

E.g. (omitting all necessary casting):

void InsertSynchronized(int slot_offset) {
  int bucket_index, cell_index, bit_index;
  SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index);
  
  AtomicWord bucket_ptr = base::Acquire_Load(&bucket[bucket_index]);
  if (bucket_ptr == nullptr) {
    uint32_t* new_bucket = AllocateBucket();
    if (!base::Release_CompareAndSwap(bucket_ptr, nullptr, new_bucket)) {
      delete new_bucket;
      bucket_ptr = base::Acquire_Load(&bucket[bucket_index]);
    }
    bucket_ptr = new_bucket;
  }

  AtomicWord old;
  do {
    old = base::Acquire_Load(&bucket_ptr[cell_index]);
  } while (!base::Release_CompareAndSwap(&bucket_ptr[cell_index], old, 1u <<
bit_index));
}

[ulan, 2016/01/28 19:07:22]

I will add this method in a separate CL as this CL is getting large.

+  }
+
+
+  // The slot offset specifies a slot at address page_start_ + slot_offset.
+  void Remove(int slot_offset) {
+    int bucket_index, cell_index, bit_index;
+    SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index);
+    if (bucket[bucket_index] != nullptr) {
+      uint32_t cell = bucket[bucket_index][cell_index];
+      if (cell) {
+        uint32_t bit_mask = 1u << bit_index;
+        if (cell & bit_mask) {
+          bucket[bucket_index][cell_index] ^= bit_mask;
+        }
+      }
+    }
+  }
+
+
+  // The slot offsets specify a range of slots at addresses:
+  // [page_start_ + start_offset ... page_start_ + end_offset).
+  void RemoveRange(int start_offset, int end_offset) {

[Michael Lippautz, 2016/01/21 10:07:32]

Amazing function :)

+    DCHECK_LE(start_offset, end_offset);
+    int start_bucket, start_cell, start_bit;
+    SlotToIndices(start_offset, &start_bucket, &start_cell, &start_bit);
+    int end_bucket, end_cell, end_bit;
+    SlotToIndices(end_offset, &end_bucket, &end_cell, &end_bit);
+    uint32_t start_mask = (1u << start_bit) - 1;
+    uint32_t end_mask = (1u << end_bit) - 1;

[Hannes Payer (out of office), 2016/01/20 19:43:00]

~(1u << end_bit) - 1) will give you the right end_mask right away.

[Michael Lippautz, 2016/01/21 10:07:32]

Probably doesn't matter too much, but you could also move start_mask and
end_mask into the branch.

[ulan, 2016/01/28 19:07:22]

The masks are used below too.

[ulan, 2016/01/28 19:07:22]

Done.

+    if (start_bucket == end_bucket && start_cell == end_cell) {
+      MaskCell(start_bucket, start_cell, start_mask | ~end_mask);
+      return;
+    }
+    MaskCell(start_bucket, start_cell, start_mask);
+    start_cell++;
+    if (bucket[start_bucket] != nullptr && start_bucket < end_bucket) {
+      while (start_cell < kCellsPerBucket) {
+        bucket[start_bucket][start_cell] = 0;
+        start_cell++;
+      }
+    }
+    while (start_bucket < end_bucket) {
+      delete[] bucket[start_bucket];
+      bucket[start_bucket] = nullptr;
+      start_bucket++;
+    }
+    if (bucket[start_bucket] != nullptr) {
+      while (start_cell < end_cell) {
+        bucket[start_bucket][start_cell] = 0;
+        start_cell++;
+      }
+    }
+    MaskCell(end_bucket, end_cell, ~end_mask);
+  }
+
+
+  // The slot offset specifies a slot at address page_start_ + slot_offset.
+  bool Lookup(int slot_offset) {
+    int bucket_index, cell_index, bit_index;
+    SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index);
+    if (bucket[bucket_index] != nullptr) {
+      uint32_t cell = bucket[bucket_index][cell_index];
+      return (cell & (1u << bit_index)) != 0;
+    }
+    return false;
+  }
+
+
+  enum CallbackResult { KEEP_SLOT, REMOVE_SLOT };

[Michael Lippautz, 2016/01/21 10:07:32]

nit: Move to top

[ulan, 2016/01/28 19:07:22]

Done.

+
+
+  // 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.
+  //
+  // Sample usage:
+  // Iterate([](Address slot_address) {
+  //    if (good(slot_address)) return KEEP_SLOT;
+  //    else return REMOVE_SLOT;
+  // });
+  template <typename Callback>
+  void Iterate(Callback callback) {
+    for (int bucket_index = 0; bucket_index < kBuckets; bucket_index++) {
+      if (bucket[bucket_index] != nullptr) {
+        bool bucket_is_empty = true;
+        uint32_t* current_bucket = bucket[bucket_index];
+        int cell_offset = bucket_index * kBitsPerBucket;
+        for (int i = 0; i < kCellsPerBucket; i++, cell_offset += kBitsPerCell) {
+          if (current_bucket[i]) {
+            uint32_t cell = current_bucket[i];
+            uint32_t old_cell = cell;
+            uint32_t new_cell = cell;
+            while (cell) {
+              int bit_offset = base::bits::CountTrailingZeros32(cell);
+              uint32_t bit_mask = 1u << bit_offset;
+              uint32_t slot = (cell_offset + bit_offset) << kPointerSizeLog2;
+              if (callback(page_start_ + slot) == KEEP_SLOT) {
+                bucket_is_empty = false;
+              } else {
+                new_cell ^= bit_mask;
+              }
+              cell ^= bit_mask;
+            }
+            if (old_cell != new_cell) {
+              current_bucket[i] = new_cell;
+            }
+          }
+        }
+        if (bucket_is_empty) {
+          ReleaseBucket(bucket_index);
+        }
+      }
+    }
+  }
+
+ private:
+  uint32_t* AllocateBucket() {
+    uint32_t* result = new uint32_t[kCellsPerBucket];

[Hannes Payer (out of office), 2016/01/20 19:43:00]

This is a nice way to safe memory, but it may be potentially bad for cache
locality. A similar approach would be to have all the cells virtually allocated
but unmap unused physical cells. That would require kCellsPerBucket = 128 to
unmap physical 4K pages.
WDYT? Let's discuss this offline.

[Michael Lippautz, 2016/01/21 10:07:32]

nit: If you use NewArray<uint32_t>(kCellsPerBucket) you get the benefit of
checking the memory against null. I guess the performance impact should be
negligible.

[ulan, 2016/01/28 19:07:22]

Done.

[ulan, 2016/01/28 19:07:22]

Ack. Let's discuss offline.

+    for (int i = 0; i < kCellsPerBucket; i++) {
+      result[i] = 0;
+    }
+    return result;
+  }
+
+
+  void ReleaseBucket(int bucket_index) {
+    delete[] bucket[bucket_index];
+    bucket[bucket_index] = nullptr;
+  }
+
+
+  void MaskCell(int bucket_index, int cell_index, uint32_t mask) {
+    uint32_t* cells = bucket[bucket_index];
+    if (cells != nullptr && cells[cell_index] != 0) {

[Michael Lippautz, 2016/01/21 10:07:32]

AFAIC this could just be DCHECKs, e.g.,
  DCHECK_NOT_NULL(cells);
  DCHECK_NE(cells[cell_index], 0);

(I would do the masking unconditionally of the value of cells[cell_index])

[ulan, 2016/01/28 19:07:22]

The cells and cell[cell_index] can be 0.

+      cells[cell_index] &= mask;
+    }
+  }
+
+
+  // Converts the slot offset into bucket/cell/bit index.
+  void SlotToIndices(int slot_offset, int* bucket_index, int* cell_index,
+                     int* bit_index) {

[Hannes Payer (out of office), 2016/01/20 19:43:00]

Can we DCHECK that slot_offset is within the page?

[ulan, 2016/01/28 19:07:22]

The equivalent DCHECK is performed below for slot.

+    DCHECK(slot_offset % kPointerSize == 0);

[Michael Lippautz, 2016/01/21 10:07:32]

nit: DCHECK_EQ

[ulan, 2016/01/28 19:07:22]

Done.

+    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);
+  }
+
+  static const int kMaxSlots = (1 << kPageSizeBits) / kPointerSize;

[Michael Lippautz, 2016/01/21 10:07:32]

nit: Move right below the "private:" section.

[ulan, 2016/01/28 19:07:22]

Done.

+  static const int kCellsPerBucket = 64;
+  static const int kCellsPerBucketLog2 = 6;
+  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;
+
+
+  uint32_t* bucket[kBuckets];
+  Address page_start_;
+};
+
+
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_SLOT_SET_H