Made zone segments aligned in memory and included a pointer to the zone in the header. Larger objec…

src/zone.cc

 // Copyright 2012 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.
 
 #include "src/zone.h"
 
 #include <cstring>
 
 #include "src/v8.h"
 
@@ skipping 25 matching lines @@
   } while (false)
 
 const size_t kASanRedzoneBytes = 0;
 
 #endif  // V8_USE_ADDRESS_SANITIZER
 
 }  // namespace
 
 
 // Segments represent chunks of memory: They have starting address
-// (encoded in the this pointer) and a size in bytes. Segments are
+// (encoded in the this pointer) and a VirtualMemory instance. Segments are
 // chained together forming a LIFO structure with the newest segment
-// available as segment_head_. Segments are allocated using malloc()
-// and de-allocated using free().
+// available as segment_head_. Segments are allocated aligned via the
+// VirtualMemory instance and released using it.
 
 class Segment {
  public:
-  void Initialize(Segment* next, size_t size) {
-    next_ = next;
-    size_ = size;
+  void Initialize(Zone* zone, v8::base::VirtualMemory* virtual_memory) {
+    DCHECK_EQ(reinterpret_cast<uintptr_t>(this) & Zone::kSegmentAlignmentMask,
+              reinterpret_cast<uintptr_t>(this));
+
+    next_ = nullptr;
+    zone_ = zone;
+    virtual_memory_.Reset();
+    virtual_memory_.TakeControl(virtual_memory);
   }
 
+  Zone* zone() const { return zone_; }
   Segment* next() const { return next_; }
-  void clear_next() { next_ = nullptr; }
+  void set_next(Segment* const value) { next_ = value; }
 
-  size_t size() const { return size_; }
-  size_t capacity() const { return size_ - sizeof(Segment); }
+  size_t size() const { return virtual_memory_.size(); }
+
+  size_t capacity() const { return size() - sizeof(Segment); }
 
   Address start() const { return address(sizeof(Segment)); }
-  Address end() const { return address(size_); }
+  Address end() const { return address(size()); }
+
+  bool is_big_object_segment() const {
+    return size() > Zone::kMaximumSegmentSize;
+  }
+
+  void Release() {
+    v8::base::VirtualMemory vm = v8::base::VirtualMemory();
+    vm.TakeControl(&virtual_memory_);

[Jakob Kummerow, 2016/09/02 14:11:49]

Why is this dance necessary, as opposed to calling virtual_memory_.Release()
directly?

[heimbuef, 2016/09/05 12:38:15]

Because of the `memset` below. `virtual_memory_` will be zapped by that and we
would have no way to release it then. Of course I could move 'the dance' in the
conditional area.

+
+#ifdef ENABLE_HANDLE_ZAPPING
+    // Un-poison first so the zapping doesn't trigger ASan complaints.
+    ASAN_UNPOISON_MEMORY_REGION(vm.address(), vm.size());
+    // Zap the entire current segment (including the header).
+    memset(vm.address(), kZapDeadByte, vm.size());
+#endif
+
+    vm.Release();
+  }
+
+  void Reset() {
+    // Un-poison so neither the zapping not the reusing does trigger ASan
+    // complaints.
+    ASAN_UNPOISON_MEMORY_REGION(virtual_memory_.address(),
+                                virtual_memory_.size());
+#ifdef DEBUG
+    // Zap the entire current segment (including the header).
+    memset(reinterpret_cast<void*>(start()), kZapDeadByte, capacity());
+#endif
+    next_ = nullptr;
+  }
 
  private:
+#ifdef DEBUG
+  // Constant byte value used for zapping dead memory in debug mode.
+  static const unsigned char kZapDeadByte = 0xcd;
+#endif
+
   // Computes the address of the nth byte in this segment.
   Address address(size_t n) const { return Address(this) + n; }
 
+  Zone* zone_;
   Segment* next_;
-  size_t size_;
+  v8::base::VirtualMemory virtual_memory_;
+
+  DISALLOW_COPY_AND_ASSIGN(Segment);
 };
 
 Zone::Zone(base::AccountingAllocator* allocator)
     : allocation_size_(0),
       segment_bytes_allocated_(0),
       position_(0),
       limit_(0),
       allocator_(allocator),
       segment_head_(nullptr) {}
 
 Zone::~Zone() {
   DeleteAll();
   DeleteKeptSegment();
 
   DCHECK(segment_bytes_allocated_ == 0);
 }
 
+Segment* Zone::GetZoneSegmentFromPointer(const void* ptr) {
+  return reinterpret_cast<Segment*>(reinterpret_cast<uintptr_t>(ptr) &
+                                    kSegmentAlignmentMask);
+}
+
+Zone* Zone::GetZoneFromPointer(const void* ptr) {
+  return GetZoneSegmentFromPointer(ptr)->zone();
+}
 
 void* Zone::New(size_t size) {
+  Address result = position_;
+
+  // corner case: zero size

[Jakob Kummerow, 2016/09/02 14:11:48]

nit: Comments should have proper capitalization, grammar, and punctuation.
(Again below.)

[heimbuef, 2016/09/05 12:38:15]

Acknowledged.

+  if (size == 0) {

[Jakob Kummerow, 2016/09/02 14:11:48]

Does this ever happen?

[heimbuef, 2016/09/05 12:38:15]

Yes, quite frequently. I also plan on using it myself in `ZoneList` to include a
`Zone`-pointer in each `ZoneList` even if we do not want to get any capacity
just yet.

+    // there has to be a normal segment to reference
+    if (segment_head_ == nullptr || segment_head_->is_big_object_segment()) {
+      // we allocate a segment of minimal size
+      result = NewNormalSegment(kAlignment);
+    }
+
+    DCHECK(!GetZoneSegmentFromPointer(result)->is_big_object_segment());
+    DCHECK_EQ(GetZoneFromPointer(result), this);
+    return reinterpret_cast<void*>(result);
+  }
+
+  // Large objects are a special case and get their own segment to live in.
+  if (CalculateSegmentSize(size) > kMaximumSegmentSize) {
+    result = NewLargeObjectSegment(size);
+    DCHECK(GetZoneSegmentFromPointer(result)->is_big_object_segment());
+    return reinterpret_cast<void*>(result);
+  }
+
   // Round up the requested size to fit the alignment.
   size = RoundUp(size, kAlignment);
 
   // If the allocation size is divisible by 8 then we return an 8-byte aligned
   // address.
   if (kPointerSize == 4 && kAlignment == 4) {
     position_ += ((~size) & 4) & (reinterpret_cast<intptr_t>(position_) & 4);
   } else {
     DCHECK(kAlignment >= kPointerSize);
   }
 
   // Check if the requested size is available without expanding.
-  Address result = position_;
 
   const size_t size_with_redzone = size + kASanRedzoneBytes;
   const uintptr_t limit = reinterpret_cast<uintptr_t>(limit_);
   const uintptr_t position = reinterpret_cast<uintptr_t>(position_);
   // position_ > limit_ can be true after the alignment correction above.
   if (limit < position || size_with_redzone > limit - position) {
-    result = NewExpand(size_with_redzone);
+    result = NewNormalSegment(size_with_redzone);
   } else {
     position_ += size_with_redzone;
   }
 
   Address redzone_position = result + size;
   DCHECK(redzone_position + kASanRedzoneBytes == position_);
   ASAN_POISON_MEMORY_REGION(redzone_position, kASanRedzoneBytes);
 
   // Check that the result has the proper alignment and return it.
   DCHECK(IsAddressAligned(result, kAlignment, 0));
+  DCHECK(!GetZoneSegmentFromPointer(result)->is_big_object_segment());
+  DCHECK_EQ(GetZoneFromPointer(result), this);
   allocation_size_ += size;
   return reinterpret_cast<void*>(result);
 }
 
 
 void Zone::DeleteAll() {
-#ifdef DEBUG
-  // Constant byte value used for zapping dead memory in debug mode.
-  static const unsigned char kZapDeadByte = 0xcd;
-#endif
-
   // Find a segment with a suitable size to keep around.
   Segment* keep = nullptr;
   // Traverse the chained list of segments, zapping (in debug mode)
   // and freeing every segment except the one we wish to keep.
   for (Segment* current = segment_head_; current;) {
     Segment* next = current->next();
     if (!keep && current->size() <= kMaximumKeptSegmentSize) {
       // Unlink the segment we wish to keep from the list.
       keep = current;
-      keep->clear_next();
+      keep->Reset();
     } else {
-      size_t size = current->size();
-#ifdef DEBUG
-      // Un-poison first so the zapping doesn't trigger ASan complaints.
-      ASAN_UNPOISON_MEMORY_REGION(current, size);
-      // Zap the entire current segment (including the header).
-      memset(current, kZapDeadByte, size);
-#endif
-      DeleteSegment(current, size);
+      segment_bytes_allocated_ -= current->size();
+      allocator_->ChangeCurrentMemoryUsage(
+          -static_cast<int64_t>(current->size()));
+      current->Release();
     }
     current = next;
   }
 
   // If we have found a segment we want to keep, we must recompute the
   // variables 'position' and 'limit' to prepare for future allocate
   // attempts. Otherwise, we must clear the position and limit to
   // force a new segment to be allocated on demand.
   if (keep) {
     Address start = keep->start();
     position_ = RoundUp(start, kAlignment);
     limit_ = keep->end();
-    // Un-poison so we can re-use the segment later.
-    ASAN_UNPOISON_MEMORY_REGION(start, keep->capacity());
-#ifdef DEBUG
-    // Zap the contents of the kept segment (but not the header).
-    memset(start, kZapDeadByte, keep->capacity());
-#endif
   } else {
     position_ = limit_ = 0;
   }
 
   allocation_size_ = 0;
   // Update the head segment to be the kept segment (if any).
   segment_head_ = keep;
 }
 
 
 void Zone::DeleteKeptSegment() {
-#ifdef DEBUG
-  // Constant byte value used for zapping dead memory in debug mode.
-  static const unsigned char kZapDeadByte = 0xcd;
-#endif
-
   DCHECK(segment_head_ == nullptr || segment_head_->next() == nullptr);
   if (segment_head_ != nullptr) {
-    size_t size = segment_head_->size();
-#ifdef DEBUG
-    // Un-poison first so the zapping doesn't trigger ASan complaints.
-    ASAN_UNPOISON_MEMORY_REGION(segment_head_, size);
-    // Zap the entire kept segment (including the header).
-    memset(segment_head_, kZapDeadByte, size);
-#endif
-    DeleteSegment(segment_head_, size);
+    segment_bytes_allocated_ -= segment_head_->size();
+    allocator_->ChangeCurrentMemoryUsage(
+        -static_cast<int64_t>(segment_head_->size()));
+    segment_head_->Release();
     segment_head_ = nullptr;
   }
 
   DCHECK(segment_bytes_allocated_ == 0);
 }
 
 
-// Creates a new segment, sets it size, and pushes it to the front
-// of the segment chain. Returns the new segment.
 Segment* Zone::NewSegment(size_t size) {
-  Segment* result = reinterpret_cast<Segment*>(allocator_->Allocate(size));
-  segment_bytes_allocated_ += size;
-  if (result != nullptr) {
-    result->Initialize(segment_head_, size);
-    segment_head_ = result;
+  v8::base::VirtualMemory vm(size, kSegmentAlignmentSize);
+
+  if (vm.IsReserved()) {

[Jakob Kummerow, 2016/09/02 14:11:49]

style nit: I'd reverse the condition to both make it clearer what the regular
code path is, and avoid unnecessary indentation, i.e.:

if (!vm.IsReserved()) {
  V8::FatalProcessOutOfMemory("Zone");
  return nullptr;
}
// Continue on this level.

[heimbuef, 2016/09/05 12:38:15]

Acknowledged.

+    DCHECK_EQ(reinterpret_cast<uintptr_t>(vm.address()) & kSegmentAlignmentMask,
+              reinterpret_cast<uintptr_t>(vm.address()));
+    DCHECK_EQ(vm.size(), size);
+    v8::base::VirtualMemory::CommitRegion(vm.address(), vm.size(), false);

[Jakob Kummerow, 2016/09/02 14:11:48]

This can fail! You must call FatalProcessOutOfMemory() when it returns false.

[heimbuef, 2016/09/05 12:38:15]

Acknowledged.

+
+    Segment* result = reinterpret_cast<Segment*>(vm.address());
+
+    result->Initialize(this, &vm);
+
+    segment_bytes_allocated_ += result->size();
+    allocator_->ChangeCurrentMemoryUsage(result->size());
+
+    return result;
+  } else {
+    V8::FatalProcessOutOfMemory("Zone");
+    return nullptr;
   }
+}
+
+Address Zone::NewLargeObjectSegment(size_t size) {
+  size_t new_size = CalculateSegmentSize(size);
+  Segment* segment = NewSegment(new_size);
+
+  if (segment_head_ == nullptr) {
+    // corner case in which a large object segment becomes the head

[Jakob Kummerow, 2016/09/02 14:11:48]

nit: capitalization please

[heimbuef, 2016/09/05 12:38:15]

Acknowledged.

+    // of the segment list.
+    segment_head_ = segment;
+  } else {
+    // large object segments should be inserted second into the list

[Jakob Kummerow, 2016/09/02 14:11:48]

again, and punctuation

[heimbuef, 2016/09/05 12:38:15]

Acknowledged.

+    segment->set_next(segment_head_->next());
+    segment_head_->set_next(segment);
+  }
+
+  Address result = RoundUp(segment->start(), kAlignment);
+  DCHECK_EQ(GetZoneFromPointer(segment), this);
+  DCHECK_EQ(GetZoneFromPointer(result), this);
   return result;
 }
 
-
-// Deletes the given segment. Does not touch the segment chain.
-void Zone::DeleteSegment(Segment* segment, size_t size) {
-  segment_bytes_allocated_ -= size;
-  allocator_->Free(segment, size);
-}
-
-
-Address Zone::NewExpand(size_t size) {
+Address Zone::NewNormalSegment(size_t size) {
   // Make sure the requested size is already properly aligned and that
   // there isn't enough room in the Zone to satisfy the request.
   DCHECK_EQ(size, RoundDown(size, kAlignment));
   DCHECK(limit_ < position_ ||
          reinterpret_cast<uintptr_t>(limit_) -
                  reinterpret_cast<uintptr_t>(position_) <
              size);
 
-  // Compute the new segment size. We use a 'high water mark'
-  // strategy, where we increase the segment size every time we expand
-  // except that we employ a maximum segment size when we delete. This
-  // is to avoid excessive malloc() and free() overhead.
-  Segment* head = segment_head_;
-  const size_t old_size = (head == nullptr) ? 0 : head->size();
-  static const size_t kSegmentOverhead = sizeof(Segment) + kAlignment;
-  const size_t new_size_no_overhead = size + (old_size << 1);
-  size_t new_size = kSegmentOverhead + new_size_no_overhead;
-  const size_t min_new_size = kSegmentOverhead + size;
-  // Guard against integer overflow.
-  if (new_size_no_overhead < size || new_size < kSegmentOverhead) {
-    V8::FatalProcessOutOfMemory("Zone");
-    return nullptr;
-  }
-  if (new_size < kMinimumSegmentSize) {
-    new_size = kMinimumSegmentSize;
-  } else if (new_size > kMaximumSegmentSize) {
-    // Limit the size of new segments to avoid growing the segment size
-    // exponentially, thus putting pressure on contiguous virtual address space.
-    // All the while making sure to allocate a segment large enough to hold the
-    // requested size.
-    new_size = Max(min_new_size, kMaximumSegmentSize);
-  }
-  if (new_size > INT_MAX) {
-    V8::FatalProcessOutOfMemory("Zone");
-    return nullptr;
-  }
+  // Only normal segments here

[Jakob Kummerow, 2016/09/02 14:11:49]

nit: punctuation, again several times below

[heimbuef, 2016/09/05 12:38:15]

Acknowledged.

+  DCHECK_LE(size, kMaximumSegmentSize + 0);

[Jakob Kummerow, 2016/09/02 14:11:48]

why "+ 0"?

[heimbuef, 2016/09/05 12:38:15]

Because the Macro does not compile otherwise. I can include a comment if you
want to, but the Macro just seems broken if you ask me. Feel free to
investigate.

+
+  size_t new_size = CalculateSegmentSize(size);
+  const size_t old_size =
+      (segment_head_ == nullptr) ? 0 : segment_head_->size();
+  new_size = Max(new_size, old_size << 1);
+  new_size = Min(new_size, kMaximumSegmentSize);
+
+  // Rounding up shall not mess with our limits
+  DCHECK_LE(new_size, kMaximumSegmentSize + 0);
+
   Segment* segment = NewSegment(new_size);
-  if (segment == nullptr) {
-    V8::FatalProcessOutOfMemory("Zone");
-    return nullptr;
-  }
+
+  // Put in front of the segment list
+  segment->set_next(segment_head_);
+  segment_head_ = segment;
+
+  // Normal segments must not be bigger than the alignment size
+  DCHECK_LE(segment->size(), kSegmentAlignmentSize + 0);
 
   // Recompute 'top' and 'limit' based on the new segment.
   Address result = RoundUp(segment->start(), kAlignment);
   position_ = result + size;
   // Check for address overflow.
   // (Should not happen since the segment is guaranteed to accomodate
   // size bytes + header and alignment padding)
-  DCHECK(reinterpret_cast<uintptr_t>(position_) >=
-         reinterpret_cast<uintptr_t>(result));
+  DCHECK_GE(reinterpret_cast<uintptr_t>(position_),
+            reinterpret_cast<uintptr_t>(result));
+  DCHECK_EQ(GetZoneFromPointer(segment), this);
+  DCHECK_EQ(GetZoneFromPointer(result), this);
+  DCHECK_EQ(GetZoneFromPointer(segment->end() - 1), this);
   limit_ = segment->end();
   DCHECK(position_ <= limit_);
   return result;
 }
 
+size_t Zone::CalculateSegmentSize(const size_t requested) {
+  if (UINTPTR_MAX - (sizeof(Segment) + kAlignment) < requested) {
+    V8::FatalProcessOutOfMemory("Zone");
+  }
+
+  return RoundUp(requested + sizeof(Segment) + kAlignment, kMinimumSegmentSize);
+}
+
 }  // namespace internal
 }  // namespace v8