blob: 30af54d4b4807a7d21c3bebd2eed7b2e043259a5 [file] [log] [blame]
// 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.
#ifndef V8_ZONE_ZONE_H_
#define V8_ZONE_ZONE_H_
#include <algorithm>
#include <limits>
#include <vector>
#include "src/base/hashmap.h"
#include "src/base/logging.h"
#include "src/common/globals.h"
#include "src/zone/accounting-allocator.h"
#include "src/zone/zone-segment.h"
#ifndef ZONE_NAME
#define STRINGIFY(x) #x
#define TOSTRING(x) STRINGIFY(x)
#define ZONE_NAME __FILE__ ":" TOSTRING(__LINE__)
#endif
namespace v8 {
namespace internal {
// The Zone supports very fast allocation of small chunks of
// memory. The chunks cannot be deallocated individually, but instead
// the Zone supports deallocating all chunks in one fast
// operation. The Zone is used to hold temporary data structures like
// the abstract syntax tree, which is deallocated after compilation.
//
// Note: There is no need to initialize the Zone; the first time an
// allocation is attempted, a segment of memory will be requested
// through the allocator.
//
// Note: The implementation is inherently not thread safe. Do not use
// from multi-threaded code.
enum class SegmentSize { kLarge, kDefault };
class V8_EXPORT_PRIVATE Zone final {
public:
Zone(AccountingAllocator* allocator, const char* name,
SegmentSize segment_size = SegmentSize::kDefault);
~Zone();
// Allocate 'size' bytes of memory in the Zone; expands the Zone by
// allocating new segments of memory on demand using malloc().
void* New(size_t size) {
#ifdef V8_USE_ADDRESS_SANITIZER
return AsanNew(size);
#else
size = RoundUp(size, kAlignmentInBytes);
Address result = position_;
if (V8_UNLIKELY(size > limit_ - position_)) {
result = NewExpand(size);
} else {
position_ += size;
}
return reinterpret_cast<void*>(result);
#endif
}
void* AsanNew(size_t size);
template <typename T>
T* NewArray(size_t length) {
DCHECK_LT(length, std::numeric_limits<size_t>::max() / sizeof(T));
return static_cast<T*>(New(length * sizeof(T)));
}
// Seals the zone to prevent any further allocation.
void Seal() { sealed_ = true; }
// Allows the zone to be safely reused. Releases the memory and fires zone
// destruction and creation events for the accounting allocator.
void ReleaseMemory();
// Returns true if more memory has been allocated in zones than
// the limit allows.
bool excess_allocation() const {
return segment_bytes_allocated_ > kExcessLimit;
}
const char* name() const { return name_; }
size_t allocation_size() const {
size_t extra = segment_head_ ? position_ - segment_head_->start() : 0;
return allocation_size_ + extra;
}
AccountingAllocator* allocator() const { return allocator_; }
private:
// Deletes all objects and free all memory allocated in the Zone.
void DeleteAll();
// All pointers returned from New() are 8-byte aligned.
static const size_t kAlignmentInBytes = 8;
// Never allocate segments smaller than this size in bytes.
static const size_t kMinimumSegmentSize = 8 * KB;
// Never allocate segments larger than this size in bytes.
static const size_t kMaximumSegmentSize = 1 * MB;
// Report zone excess when allocation exceeds this limit.
static const size_t kExcessLimit = 256 * MB;
// The number of bytes allocated in this zone so far.
size_t allocation_size_;
// The number of bytes allocated in segments. Note that this number
// includes memory allocated from the OS but not yet allocated from
// the zone.
size_t segment_bytes_allocated_;
// Expand the Zone to hold at least 'size' more bytes and allocate
// the bytes. Returns the address of the newly allocated chunk of
// memory in the Zone. Should only be called if there isn't enough
// room in the Zone already.
Address NewExpand(size_t size);
// Creates a new segment, sets it size, and pushes it to the front
// of the segment chain. Returns the new segment.
inline Segment* NewSegment(size_t requested_size);
// The free region in the current (front) segment is represented as
// the half-open interval [position, limit). The 'position' variable
// is guaranteed to be aligned as dictated by kAlignment.
Address position_;
Address limit_;
AccountingAllocator* allocator_;
Segment* segment_head_;
const char* name_;
bool sealed_;
SegmentSize segment_size_;
};
// ZoneObject is an abstraction that helps define classes of objects
// allocated in the Zone. Use it as a base class; see ast.h.
class ZoneObject {
public:
// Allocate a new ZoneObject of 'size' bytes in the Zone.
void* operator new(size_t size, Zone* zone) { return zone->New(size); }
// Ideally, the delete operator should be private instead of
// public, but unfortunately the compiler sometimes synthesizes
// (unused) destructors for classes derived from ZoneObject, which
// require the operator to be visible. MSVC requires the delete
// operator to be public.
// ZoneObjects should never be deleted individually; use
// Zone::DeleteAll() to delete all zone objects in one go.
void operator delete(void*, size_t) { UNREACHABLE(); }
void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
};
// The ZoneAllocationPolicy is used to specialize generic data
// structures to allocate themselves and their elements in the Zone.
class ZoneAllocationPolicy final {
public:
explicit ZoneAllocationPolicy(Zone* zone) : zone_(zone) {}
void* New(size_t size) { return zone()->New(size); }
static void Delete(void* pointer) {}
Zone* zone() const { return zone_; }
private:
Zone* zone_;
};
template <typename T>
class Vector;
// ZoneLists are growable lists with constant-time access to the
// elements. The list itself and all its elements are allocated in the
// Zone. ZoneLists cannot be deleted individually; you can delete all
// objects in the Zone by calling Zone::DeleteAll().
template <typename T>
class ZoneList final {
public:
// Construct a new ZoneList with the given capacity; the length is
// always zero. The capacity must be non-negative.
ZoneList(int capacity, Zone* zone) { Initialize(capacity, zone); }
// Construct a new ZoneList from a std::initializer_list
ZoneList(std::initializer_list<T> list, Zone* zone) {
Initialize(static_cast<int>(list.size()), zone);
for (auto& i : list) Add(i, zone);
}
// Construct a new ZoneList by copying the elements of the given ZoneList.
ZoneList(const ZoneList<T>& other, Zone* zone) {
Initialize(other.length(), zone);
AddAll(other, zone);
}
V8_INLINE ~ZoneList() { DeleteData(data_); }
// Please the MSVC compiler. We should never have to execute this.
V8_INLINE void operator delete(void* p, ZoneAllocationPolicy allocator) {
UNREACHABLE();
}
void* operator new(size_t size, Zone* zone) { return zone->New(size); }
// Returns a reference to the element at index i. This reference is not safe
// to use after operations that can change the list's backing store
// (e.g. Add).
inline T& operator[](int i) const {
DCHECK_LE(0, i);
DCHECK_GT(static_cast<unsigned>(length_), static_cast<unsigned>(i));
return data_[i];
}
inline T& at(int i) const { return operator[](i); }
inline T& last() const { return at(length_ - 1); }
inline T& first() const { return at(0); }
typedef T* iterator;
inline iterator begin() const { return &data_[0]; }
inline iterator end() const { return &data_[length_]; }
V8_INLINE bool is_empty() const { return length_ == 0; }
V8_INLINE int length() const { return length_; }
V8_INLINE int capacity() const { return capacity_; }
Vector<T> ToVector() const { return Vector<T>(data_, length_); }
Vector<T> ToVector(int start, int length) const {
return Vector<T>(data_ + start, std::min(length_ - start, length));
}
Vector<const T> ToConstVector() const {
return Vector<const T>(data_, length_);
}
V8_INLINE void Initialize(int capacity, Zone* zone) {
DCHECK_GE(capacity, 0);
data_ = (capacity > 0) ? NewData(capacity, ZoneAllocationPolicy(zone))
: nullptr;
capacity_ = capacity;
length_ = 0;
}
// Adds a copy of the given 'element' to the end of the list,
// expanding the list if necessary.
void Add(const T& element, Zone* zone);
// Add all the elements from the argument list to this list.
void AddAll(const ZoneList<T>& other, Zone* zone);
// Add all the elements from the vector to this list.
void AddAll(const Vector<T>& other, Zone* zone);
// Inserts the element at the specific index.
void InsertAt(int index, const T& element, Zone* zone);
// Added 'count' elements with the value 'value' and returns a
// vector that allows access to the elements. The vector is valid
// until the next change is made to this list.
Vector<T> AddBlock(T value, int count, Zone* zone);
// Overwrites the element at the specific index.
void Set(int index, const T& element);
// Removes the i'th element without deleting it even if T is a
// pointer type; moves all elements above i "down". Returns the
// removed element. This function's complexity is linear in the
// size of the list.
T Remove(int i);
// Removes the last element without deleting it even if T is a
// pointer type. Returns the removed element.
V8_INLINE T RemoveLast() { return Remove(length_ - 1); }
// Clears the list by freeing the storage memory. If you want to keep the
// memory, use Rewind(0) instead. Be aware, that even if T is a
// pointer type, clearing the list doesn't delete the entries.
V8_INLINE void Clear();
// Drops all but the first 'pos' elements from the list.
V8_INLINE void Rewind(int pos);
inline bool Contains(const T& elm) const {
for (int i = 0; i < length_; i++) {
if (data_[i] == elm) return true;
}
return false;
}
// Iterate through all list entries, starting at index 0.
template <class Visitor>
void Iterate(Visitor* visitor);
// Sort all list entries (using QuickSort)
template <typename CompareFunction>
void Sort(CompareFunction cmp);
template <typename CompareFunction>
void StableSort(CompareFunction cmp, size_t start, size_t length);
void operator delete(void* pointer) { UNREACHABLE(); }
void operator delete(void* pointer, Zone* zone) { UNREACHABLE(); }
private:
T* data_;
int capacity_;
int length_;
V8_INLINE T* NewData(int n, ZoneAllocationPolicy allocator) {
return static_cast<T*>(allocator.New(n * sizeof(T)));
}
V8_INLINE void DeleteData(T* data) { ZoneAllocationPolicy::Delete(data); }
// Increase the capacity of a full list, and add an element.
// List must be full already.
void ResizeAdd(const T& element, ZoneAllocationPolicy allocator);
// Inlined implementation of ResizeAdd, shared by inlined and
// non-inlined versions of ResizeAdd.
void ResizeAddInternal(const T& element, ZoneAllocationPolicy allocator);
// Resize the list.
void Resize(int new_capacity, ZoneAllocationPolicy allocator);
DISALLOW_COPY_AND_ASSIGN(ZoneList);
};
// ZonePtrList is a ZoneList of pointers to ZoneObjects allocated in the same
// zone as the list object.
template <typename T>
using ZonePtrList = ZoneList<T*>;
template <typename T>
class ScopedPtrList final {
public:
explicit ScopedPtrList(std::vector<void*>* buffer)
: buffer_(*buffer), start_(buffer->size()), end_(buffer->size()) {}
~ScopedPtrList() { Rewind(); }
void Rewind() {
DCHECK_EQ(buffer_.size(), end_);
buffer_.resize(start_);
end_ = start_;
}
void MergeInto(ScopedPtrList* parent) {
DCHECK_EQ(parent->end_, start_);
parent->end_ = end_;
start_ = end_;
DCHECK_EQ(0, length());
}
int length() const { return static_cast<int>(end_ - start_); }
T* at(int i) const {
size_t index = start_ + i;
DCHECK_LE(start_, index);
DCHECK_LT(index, buffer_.size());
return reinterpret_cast<T*>(buffer_[index]);
}
void CopyTo(ZonePtrList<T>* target, Zone* zone) const {
DCHECK_LE(end_, buffer_.size());
// Make sure we don't reference absent elements below.
if (length() == 0) return;
target->Initialize(length(), zone);
T** data = reinterpret_cast<T**>(&buffer_[start_]);
target->AddAll(Vector<T*>(data, length()), zone);
}
Vector<T*> CopyTo(Zone* zone) {
DCHECK_LE(end_, buffer_.size());
T** data = zone->NewArray<T*>(length());
if (length() != 0) {
MemCopy(data, &buffer_[start_], length() * sizeof(T*));
}
return Vector<T*>(data, length());
}
void Add(T* value) {
DCHECK_EQ(buffer_.size(), end_);
buffer_.push_back(value);
++end_;
}
void AddAll(const ZonePtrList<T>& list) {
DCHECK_EQ(buffer_.size(), end_);
buffer_.reserve(buffer_.size() + list.length());
for (int i = 0; i < list.length(); i++) {
buffer_.push_back(list.at(i));
}
end_ += list.length();
}
typedef T** iterator;
inline iterator begin() const {
return reinterpret_cast<T**>(buffer_.data() + start_);
}
inline iterator end() const {
return reinterpret_cast<T**>(buffer_.data() + end_);
}
private:
std::vector<void*>& buffer_;
size_t start_;
size_t end_;
};
typedef base::PointerTemplateHashMapImpl<ZoneAllocationPolicy> ZoneHashMap;
typedef base::CustomMatcherTemplateHashMapImpl<ZoneAllocationPolicy>
CustomMatcherZoneHashMap;
} // namespace internal
} // namespace v8
// The accidential pattern
// new (zone) SomeObject()
// where SomeObject does not inherit from ZoneObject leads to nasty crashes.
// This triggers a compile-time error instead.
template <class T, typename = typename std::enable_if<std::is_convertible<
T, const v8::internal::Zone*>::value>::type>
void* operator new(size_t size, T zone) {
static_assert(false && sizeof(T),
"Placement new with a zone is only permitted for classes "
"inheriting from ZoneObject");
UNREACHABLE();
}
#endif // V8_ZONE_ZONE_H_