Ben Murdoch | 3ef787d | 2012-04-12 10:51:47 +0100 | [diff] [blame] | 1 | // Copyright 2012 the V8 project authors. All rights reserved. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 4 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 5 | #include "src/zone.h" |
| 6 | |
| 7 | #include <cstring> |
Ben Murdoch | 85b7179 | 2012-04-11 18:30:58 +0100 | [diff] [blame] | 8 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 9 | #include "src/v8.h" |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 10 | |
| 11 | #ifdef V8_USE_ADDRESS_SANITIZER |
| 12 | #include <sanitizer/asan_interface.h> |
| 13 | #endif // V8_USE_ADDRESS_SANITIZER |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 14 | |
| 15 | namespace v8 { |
| 16 | namespace internal { |
| 17 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 18 | namespace { |
| 19 | |
| 20 | #if V8_USE_ADDRESS_SANITIZER |
| 21 | |
| 22 | const size_t kASanRedzoneBytes = 24; // Must be a multiple of 8. |
| 23 | |
| 24 | #else |
| 25 | |
| 26 | #define ASAN_POISON_MEMORY_REGION(start, size) \ |
| 27 | do { \ |
| 28 | USE(start); \ |
| 29 | USE(size); \ |
| 30 | } while (false) |
| 31 | |
| 32 | #define ASAN_UNPOISON_MEMORY_REGION(start, size) \ |
| 33 | do { \ |
| 34 | USE(start); \ |
| 35 | USE(size); \ |
| 36 | } while (false) |
| 37 | |
| 38 | const size_t kASanRedzoneBytes = 0; |
| 39 | |
| 40 | #endif // V8_USE_ADDRESS_SANITIZER |
| 41 | |
| 42 | } // namespace |
| 43 | |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 44 | |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 45 | // Segments represent chunks of memory: They have starting address |
| 46 | // (encoded in the this pointer) and a size in bytes. Segments are |
| 47 | // chained together forming a LIFO structure with the newest segment |
Steve Block | 44f0eee | 2011-05-26 01:26:41 +0100 | [diff] [blame] | 48 | // available as segment_head_. Segments are allocated using malloc() |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 49 | // and de-allocated using free(). |
| 50 | |
| 51 | class Segment { |
| 52 | public: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 53 | void Initialize(Segment* next, size_t size) { |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 54 | next_ = next; |
| 55 | size_ = size; |
| 56 | } |
| 57 | |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 58 | Segment* next() const { return next_; } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 59 | void clear_next() { next_ = nullptr; } |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 60 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 61 | size_t size() const { return size_; } |
| 62 | size_t capacity() const { return size_ - sizeof(Segment); } |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 63 | |
| 64 | Address start() const { return address(sizeof(Segment)); } |
| 65 | Address end() const { return address(size_); } |
| 66 | |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 67 | private: |
| 68 | // Computes the address of the nth byte in this segment. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 69 | Address address(size_t n) const { return Address(this) + n; } |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 70 | |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 71 | Segment* next_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 72 | size_t size_; |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 73 | }; |
| 74 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 75 | Zone::Zone(base::AccountingAllocator* allocator) |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 76 | : allocation_size_(0), |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 77 | segment_bytes_allocated_(0), |
| 78 | position_(0), |
| 79 | limit_(0), |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 80 | allocator_(allocator), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 81 | segment_head_(nullptr) {} |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 82 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 83 | Zone::~Zone() { |
| 84 | DeleteAll(); |
| 85 | DeleteKeptSegment(); |
| 86 | |
| 87 | DCHECK(segment_bytes_allocated_ == 0); |
| 88 | } |
| 89 | |
| 90 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 91 | void* Zone::New(size_t size) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 92 | // Round up the requested size to fit the alignment. |
| 93 | size = RoundUp(size, kAlignment); |
| 94 | |
| 95 | // If the allocation size is divisible by 8 then we return an 8-byte aligned |
| 96 | // address. |
| 97 | if (kPointerSize == 4 && kAlignment == 4) { |
| 98 | position_ += ((~size) & 4) & (reinterpret_cast<intptr_t>(position_) & 4); |
| 99 | } else { |
| 100 | DCHECK(kAlignment >= kPointerSize); |
| 101 | } |
| 102 | |
| 103 | // Check if the requested size is available without expanding. |
| 104 | Address result = position_; |
| 105 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 106 | const size_t size_with_redzone = size + kASanRedzoneBytes; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 107 | const uintptr_t limit = reinterpret_cast<uintptr_t>(limit_); |
| 108 | const uintptr_t position = reinterpret_cast<uintptr_t>(position_); |
| 109 | // position_ > limit_ can be true after the alignment correction above. |
| 110 | if (limit < position || size_with_redzone > limit - position) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 111 | result = NewExpand(size_with_redzone); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 112 | } else { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 113 | position_ += size_with_redzone; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 114 | } |
| 115 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 116 | Address redzone_position = result + size; |
| 117 | DCHECK(redzone_position + kASanRedzoneBytes == position_); |
| 118 | ASAN_POISON_MEMORY_REGION(redzone_position, kASanRedzoneBytes); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 119 | |
| 120 | // Check that the result has the proper alignment and return it. |
| 121 | DCHECK(IsAddressAligned(result, kAlignment, 0)); |
| 122 | allocation_size_ += size; |
| 123 | return reinterpret_cast<void*>(result); |
| 124 | } |
| 125 | |
| 126 | |
| 127 | void Zone::DeleteAll() { |
| 128 | #ifdef DEBUG |
| 129 | // Constant byte value used for zapping dead memory in debug mode. |
| 130 | static const unsigned char kZapDeadByte = 0xcd; |
| 131 | #endif |
| 132 | |
| 133 | // Find a segment with a suitable size to keep around. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 134 | Segment* keep = nullptr; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 135 | // Traverse the chained list of segments, zapping (in debug mode) |
| 136 | // and freeing every segment except the one we wish to keep. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 137 | for (Segment* current = segment_head_; current;) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 138 | Segment* next = current->next(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 139 | if (!keep && current->size() <= kMaximumKeptSegmentSize) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 140 | // Unlink the segment we wish to keep from the list. |
| 141 | keep = current; |
| 142 | keep->clear_next(); |
| 143 | } else { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 144 | size_t size = current->size(); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 145 | #ifdef DEBUG |
| 146 | // Un-poison first so the zapping doesn't trigger ASan complaints. |
| 147 | ASAN_UNPOISON_MEMORY_REGION(current, size); |
| 148 | // Zap the entire current segment (including the header). |
| 149 | memset(current, kZapDeadByte, size); |
| 150 | #endif |
| 151 | DeleteSegment(current, size); |
| 152 | } |
| 153 | current = next; |
| 154 | } |
| 155 | |
| 156 | // If we have found a segment we want to keep, we must recompute the |
| 157 | // variables 'position' and 'limit' to prepare for future allocate |
| 158 | // attempts. Otherwise, we must clear the position and limit to |
| 159 | // force a new segment to be allocated on demand. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 160 | if (keep) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 161 | Address start = keep->start(); |
| 162 | position_ = RoundUp(start, kAlignment); |
| 163 | limit_ = keep->end(); |
| 164 | // Un-poison so we can re-use the segment later. |
| 165 | ASAN_UNPOISON_MEMORY_REGION(start, keep->capacity()); |
| 166 | #ifdef DEBUG |
| 167 | // Zap the contents of the kept segment (but not the header). |
| 168 | memset(start, kZapDeadByte, keep->capacity()); |
| 169 | #endif |
| 170 | } else { |
| 171 | position_ = limit_ = 0; |
| 172 | } |
| 173 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 174 | allocation_size_ = 0; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 175 | // Update the head segment to be the kept segment (if any). |
| 176 | segment_head_ = keep; |
| 177 | } |
| 178 | |
| 179 | |
| 180 | void Zone::DeleteKeptSegment() { |
| 181 | #ifdef DEBUG |
| 182 | // Constant byte value used for zapping dead memory in debug mode. |
| 183 | static const unsigned char kZapDeadByte = 0xcd; |
| 184 | #endif |
| 185 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 186 | DCHECK(segment_head_ == nullptr || segment_head_->next() == nullptr); |
| 187 | if (segment_head_ != nullptr) { |
| 188 | size_t size = segment_head_->size(); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 189 | #ifdef DEBUG |
| 190 | // Un-poison first so the zapping doesn't trigger ASan complaints. |
| 191 | ASAN_UNPOISON_MEMORY_REGION(segment_head_, size); |
| 192 | // Zap the entire kept segment (including the header). |
| 193 | memset(segment_head_, kZapDeadByte, size); |
| 194 | #endif |
| 195 | DeleteSegment(segment_head_, size); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 196 | segment_head_ = nullptr; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 197 | } |
| 198 | |
| 199 | DCHECK(segment_bytes_allocated_ == 0); |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 200 | } |
| 201 | |
| 202 | |
Steve Block | 44f0eee | 2011-05-26 01:26:41 +0100 | [diff] [blame] | 203 | // Creates a new segment, sets it size, and pushes it to the front |
| 204 | // of the segment chain. Returns the new segment. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 205 | Segment* Zone::NewSegment(size_t size) { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 206 | Segment* result = reinterpret_cast<Segment*>(allocator_->Allocate(size)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 207 | segment_bytes_allocated_ += size; |
| 208 | if (result != nullptr) { |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 209 | result->Initialize(segment_head_, size); |
Steve Block | 44f0eee | 2011-05-26 01:26:41 +0100 | [diff] [blame] | 210 | segment_head_ = result; |
| 211 | } |
| 212 | return result; |
| 213 | } |
| 214 | |
| 215 | |
| 216 | // Deletes the given segment. Does not touch the segment chain. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 217 | void Zone::DeleteSegment(Segment* segment, size_t size) { |
| 218 | segment_bytes_allocated_ -= size; |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 219 | allocator_->Free(segment, size); |
Steve Block | 44f0eee | 2011-05-26 01:26:41 +0100 | [diff] [blame] | 220 | } |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 221 | |
| 222 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 223 | Address Zone::NewExpand(size_t size) { |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 224 | // Make sure the requested size is already properly aligned and that |
| 225 | // there isn't enough room in the Zone to satisfy the request. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 226 | DCHECK_EQ(size, RoundDown(size, kAlignment)); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 227 | DCHECK(limit_ < position_ || |
| 228 | reinterpret_cast<uintptr_t>(limit_) - |
| 229 | reinterpret_cast<uintptr_t>(position_) < |
| 230 | size); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 231 | |
| 232 | // Compute the new segment size. We use a 'high water mark' |
| 233 | // strategy, where we increase the segment size every time we expand |
| 234 | // except that we employ a maximum segment size when we delete. This |
| 235 | // is to avoid excessive malloc() and free() overhead. |
Steve Block | 44f0eee | 2011-05-26 01:26:41 +0100 | [diff] [blame] | 236 | Segment* head = segment_head_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 237 | const size_t old_size = (head == nullptr) ? 0 : head->size(); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 238 | static const size_t kSegmentOverhead = sizeof(Segment) + kAlignment; |
| 239 | const size_t new_size_no_overhead = size + (old_size << 1); |
| 240 | size_t new_size = kSegmentOverhead + new_size_no_overhead; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 241 | const size_t min_new_size = kSegmentOverhead + size; |
Ben Murdoch | 589d697 | 2011-11-30 16:04:58 +0000 | [diff] [blame] | 242 | // Guard against integer overflow. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 243 | if (new_size_no_overhead < size || new_size < kSegmentOverhead) { |
Ben Murdoch | 589d697 | 2011-11-30 16:04:58 +0000 | [diff] [blame] | 244 | V8::FatalProcessOutOfMemory("Zone"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 245 | return nullptr; |
Ben Murdoch | 589d697 | 2011-11-30 16:04:58 +0000 | [diff] [blame] | 246 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 247 | if (new_size < kMinimumSegmentSize) { |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 248 | new_size = kMinimumSegmentSize; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 249 | } else if (new_size > kMaximumSegmentSize) { |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 250 | // Limit the size of new segments to avoid growing the segment size |
| 251 | // exponentially, thus putting pressure on contiguous virtual address space. |
| 252 | // All the while making sure to allocate a segment large enough to hold the |
| 253 | // requested size. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 254 | new_size = Max(min_new_size, kMaximumSegmentSize); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 255 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 256 | if (new_size > INT_MAX) { |
| 257 | V8::FatalProcessOutOfMemory("Zone"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 258 | return nullptr; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 259 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 260 | Segment* segment = NewSegment(new_size); |
| 261 | if (segment == nullptr) { |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 262 | V8::FatalProcessOutOfMemory("Zone"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 263 | return nullptr; |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 264 | } |
| 265 | |
| 266 | // Recompute 'top' and 'limit' based on the new segment. |
| 267 | Address result = RoundUp(segment->start(), kAlignment); |
| 268 | position_ = result + size; |
Ben Murdoch | 589d697 | 2011-11-30 16:04:58 +0000 | [diff] [blame] | 269 | // Check for address overflow. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 270 | // (Should not happen since the segment is guaranteed to accomodate |
| 271 | // size bytes + header and alignment padding) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 272 | DCHECK(reinterpret_cast<uintptr_t>(position_) >= |
| 273 | reinterpret_cast<uintptr_t>(result)); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 274 | limit_ = segment->end(); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 275 | DCHECK(position_ <= limit_); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 276 | return result; |
| 277 | } |
| 278 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 279 | } // namespace internal |
| 280 | } // namespace v8 |