Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 1 | // Copyright 2016 the V8 project authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #ifndef V8_SLOT_SET_H |
| 6 | #define V8_SLOT_SET_H |
| 7 | |
| 8 | #include "src/allocation.h" |
| 9 | #include "src/base/bits.h" |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 10 | #include "src/utils.h" |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 11 | |
| 12 | namespace v8 { |
| 13 | namespace internal { |
| 14 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 15 | enum SlotCallbackResult { KEEP_SLOT, REMOVE_SLOT }; |
| 16 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 17 | // Data structure for maintaining a set of slots in a standard (non-large) |
| 18 | // page. The base address of the page must be set with SetPageStart before any |
| 19 | // operation. |
| 20 | // The data structure assumes that the slots are pointer size aligned and |
| 21 | // splits the valid slot offset range into kBuckets buckets. |
| 22 | // Each bucket is a bitmap with a bit corresponding to a single slot offset. |
| 23 | class SlotSet : public Malloced { |
| 24 | public: |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 25 | SlotSet() { |
| 26 | for (int i = 0; i < kBuckets; i++) { |
| 27 | bucket[i] = nullptr; |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | ~SlotSet() { |
| 32 | for (int i = 0; i < kBuckets; i++) { |
| 33 | ReleaseBucket(i); |
| 34 | } |
| 35 | } |
| 36 | |
| 37 | void SetPageStart(Address page_start) { page_start_ = page_start; } |
| 38 | |
| 39 | // The slot offset specifies a slot at address page_start_ + slot_offset. |
| 40 | void Insert(int slot_offset) { |
| 41 | int bucket_index, cell_index, bit_index; |
| 42 | SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); |
| 43 | if (bucket[bucket_index] == nullptr) { |
| 44 | bucket[bucket_index] = AllocateBucket(); |
| 45 | } |
| 46 | bucket[bucket_index][cell_index] |= 1u << bit_index; |
| 47 | } |
| 48 | |
| 49 | // The slot offset specifies a slot at address page_start_ + slot_offset. |
| 50 | void Remove(int slot_offset) { |
| 51 | int bucket_index, cell_index, bit_index; |
| 52 | SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); |
| 53 | if (bucket[bucket_index] != nullptr) { |
| 54 | uint32_t cell = bucket[bucket_index][cell_index]; |
| 55 | if (cell) { |
| 56 | uint32_t bit_mask = 1u << bit_index; |
| 57 | if (cell & bit_mask) { |
| 58 | bucket[bucket_index][cell_index] ^= bit_mask; |
| 59 | } |
| 60 | } |
| 61 | } |
| 62 | } |
| 63 | |
| 64 | // The slot offsets specify a range of slots at addresses: |
| 65 | // [page_start_ + start_offset ... page_start_ + end_offset). |
| 66 | void RemoveRange(int start_offset, int end_offset) { |
| 67 | DCHECK_LE(start_offset, end_offset); |
| 68 | int start_bucket, start_cell, start_bit; |
| 69 | SlotToIndices(start_offset, &start_bucket, &start_cell, &start_bit); |
| 70 | int end_bucket, end_cell, end_bit; |
| 71 | SlotToIndices(end_offset, &end_bucket, &end_cell, &end_bit); |
| 72 | uint32_t start_mask = (1u << start_bit) - 1; |
| 73 | uint32_t end_mask = ~((1u << end_bit) - 1); |
| 74 | if (start_bucket == end_bucket && start_cell == end_cell) { |
| 75 | MaskCell(start_bucket, start_cell, start_mask | end_mask); |
| 76 | return; |
| 77 | } |
| 78 | int current_bucket = start_bucket; |
| 79 | int current_cell = start_cell; |
| 80 | MaskCell(current_bucket, current_cell, start_mask); |
| 81 | current_cell++; |
| 82 | if (current_bucket < end_bucket) { |
| 83 | if (bucket[current_bucket] != nullptr) { |
| 84 | while (current_cell < kCellsPerBucket) { |
| 85 | bucket[current_bucket][current_cell] = 0; |
| 86 | current_cell++; |
| 87 | } |
| 88 | } |
| 89 | // The rest of the current bucket is cleared. |
| 90 | // Move on to the next bucket. |
| 91 | current_bucket++; |
| 92 | current_cell = 0; |
| 93 | } |
| 94 | DCHECK(current_bucket == end_bucket || |
| 95 | (current_bucket < end_bucket && current_cell == 0)); |
| 96 | while (current_bucket < end_bucket) { |
| 97 | ReleaseBucket(current_bucket); |
| 98 | current_bucket++; |
| 99 | } |
| 100 | // All buckets between start_bucket and end_bucket are cleared. |
| 101 | DCHECK(current_bucket == end_bucket && current_cell <= end_cell); |
| 102 | if (current_bucket == kBuckets || bucket[current_bucket] == nullptr) { |
| 103 | return; |
| 104 | } |
| 105 | while (current_cell < end_cell) { |
| 106 | bucket[current_bucket][current_cell] = 0; |
| 107 | current_cell++; |
| 108 | } |
| 109 | // All cells between start_cell and end_cell are cleared. |
| 110 | DCHECK(current_bucket == end_bucket && current_cell == end_cell); |
| 111 | MaskCell(end_bucket, end_cell, end_mask); |
| 112 | } |
| 113 | |
| 114 | // The slot offset specifies a slot at address page_start_ + slot_offset. |
| 115 | bool Lookup(int slot_offset) { |
| 116 | int bucket_index, cell_index, bit_index; |
| 117 | SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); |
| 118 | if (bucket[bucket_index] != nullptr) { |
| 119 | uint32_t cell = bucket[bucket_index][cell_index]; |
| 120 | return (cell & (1u << bit_index)) != 0; |
| 121 | } |
| 122 | return false; |
| 123 | } |
| 124 | |
| 125 | // Iterate over all slots in the set and for each slot invoke the callback. |
| 126 | // If the callback returns REMOVE_SLOT then the slot is removed from the set. |
| 127 | // Returns the new number of slots. |
| 128 | // |
| 129 | // Sample usage: |
| 130 | // Iterate([](Address slot_address) { |
| 131 | // if (good(slot_address)) return KEEP_SLOT; |
| 132 | // else return REMOVE_SLOT; |
| 133 | // }); |
| 134 | template <typename Callback> |
| 135 | int Iterate(Callback callback) { |
| 136 | int new_count = 0; |
| 137 | for (int bucket_index = 0; bucket_index < kBuckets; bucket_index++) { |
| 138 | if (bucket[bucket_index] != nullptr) { |
| 139 | int in_bucket_count = 0; |
| 140 | uint32_t* current_bucket = bucket[bucket_index]; |
| 141 | int cell_offset = bucket_index * kBitsPerBucket; |
| 142 | for (int i = 0; i < kCellsPerBucket; i++, cell_offset += kBitsPerCell) { |
| 143 | if (current_bucket[i]) { |
| 144 | uint32_t cell = current_bucket[i]; |
| 145 | uint32_t old_cell = cell; |
| 146 | uint32_t new_cell = cell; |
| 147 | while (cell) { |
| 148 | int bit_offset = base::bits::CountTrailingZeros32(cell); |
| 149 | uint32_t bit_mask = 1u << bit_offset; |
| 150 | uint32_t slot = (cell_offset + bit_offset) << kPointerSizeLog2; |
| 151 | if (callback(page_start_ + slot) == KEEP_SLOT) { |
| 152 | ++in_bucket_count; |
| 153 | } else { |
| 154 | new_cell ^= bit_mask; |
| 155 | } |
| 156 | cell ^= bit_mask; |
| 157 | } |
| 158 | if (old_cell != new_cell) { |
| 159 | current_bucket[i] = new_cell; |
| 160 | } |
| 161 | } |
| 162 | } |
| 163 | if (in_bucket_count == 0) { |
| 164 | ReleaseBucket(bucket_index); |
| 165 | } |
| 166 | new_count += in_bucket_count; |
| 167 | } |
| 168 | } |
| 169 | return new_count; |
| 170 | } |
| 171 | |
| 172 | private: |
| 173 | static const int kMaxSlots = (1 << kPageSizeBits) / kPointerSize; |
| 174 | static const int kCellsPerBucket = 32; |
| 175 | static const int kCellsPerBucketLog2 = 5; |
| 176 | static const int kBitsPerCell = 32; |
| 177 | static const int kBitsPerCellLog2 = 5; |
| 178 | static const int kBitsPerBucket = kCellsPerBucket * kBitsPerCell; |
| 179 | static const int kBitsPerBucketLog2 = kCellsPerBucketLog2 + kBitsPerCellLog2; |
| 180 | static const int kBuckets = kMaxSlots / kCellsPerBucket / kBitsPerCell; |
| 181 | |
| 182 | uint32_t* AllocateBucket() { |
| 183 | uint32_t* result = NewArray<uint32_t>(kCellsPerBucket); |
| 184 | for (int i = 0; i < kCellsPerBucket; i++) { |
| 185 | result[i] = 0; |
| 186 | } |
| 187 | return result; |
| 188 | } |
| 189 | |
| 190 | void ReleaseBucket(int bucket_index) { |
| 191 | DeleteArray<uint32_t>(bucket[bucket_index]); |
| 192 | bucket[bucket_index] = nullptr; |
| 193 | } |
| 194 | |
| 195 | void MaskCell(int bucket_index, int cell_index, uint32_t mask) { |
| 196 | uint32_t* cells = bucket[bucket_index]; |
| 197 | if (cells != nullptr && cells[cell_index] != 0) { |
| 198 | cells[cell_index] &= mask; |
| 199 | } |
| 200 | } |
| 201 | |
| 202 | // Converts the slot offset into bucket/cell/bit index. |
| 203 | void SlotToIndices(int slot_offset, int* bucket_index, int* cell_index, |
| 204 | int* bit_index) { |
| 205 | DCHECK_EQ(slot_offset % kPointerSize, 0); |
| 206 | int slot = slot_offset >> kPointerSizeLog2; |
| 207 | DCHECK(slot >= 0 && slot <= kMaxSlots); |
| 208 | *bucket_index = slot >> kBitsPerBucketLog2; |
| 209 | *cell_index = (slot >> kBitsPerCellLog2) & (kCellsPerBucket - 1); |
| 210 | *bit_index = slot & (kBitsPerCell - 1); |
| 211 | } |
| 212 | |
| 213 | uint32_t* bucket[kBuckets]; |
| 214 | Address page_start_; |
| 215 | }; |
| 216 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 217 | enum SlotType { |
| 218 | EMBEDDED_OBJECT_SLOT, |
| 219 | OBJECT_SLOT, |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 220 | CELL_TARGET_SLOT, |
| 221 | CODE_TARGET_SLOT, |
| 222 | CODE_ENTRY_SLOT, |
| 223 | DEBUG_TARGET_SLOT, |
| 224 | NUMBER_OF_SLOT_TYPES |
| 225 | }; |
| 226 | |
| 227 | // Data structure for maintaining a multiset of typed slots in a page. |
| 228 | // Typed slots can only appear in Code and JSFunction objects, so |
| 229 | // the maximum possible offset is limited by the LargePage::kMaxCodePageSize. |
| 230 | // The implementation is a chain of chunks, where each chunks is an array of |
| 231 | // encoded (slot type, slot offset) pairs. |
| 232 | // There is no duplicate detection and we do not expect many duplicates because |
| 233 | // typed slots contain V8 internal pointers that are not directly exposed to JS. |
| 234 | class TypedSlotSet { |
| 235 | public: |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame^] | 236 | struct TypedSlot { |
| 237 | TypedSlot() : type_and_offset_(0), host_offset_(0) {} |
| 238 | |
| 239 | TypedSlot(SlotType type, uint32_t host_offset, uint32_t offset) |
| 240 | : type_and_offset_(TypeField::encode(type) | |
| 241 | OffsetField::encode(offset)), |
| 242 | host_offset_(host_offset) {} |
| 243 | |
| 244 | bool operator==(const TypedSlot other) { |
| 245 | return type_and_offset_ == other.type_and_offset_ && |
| 246 | host_offset_ == other.host_offset_; |
| 247 | } |
| 248 | |
| 249 | bool operator!=(const TypedSlot other) { return !(*this == other); } |
| 250 | |
| 251 | SlotType type() { return TypeField::decode(type_and_offset_); } |
| 252 | |
| 253 | uint32_t offset() { return OffsetField::decode(type_and_offset_); } |
| 254 | |
| 255 | uint32_t host_offset() { return host_offset_; } |
| 256 | |
| 257 | uint32_t type_and_offset_; |
| 258 | uint32_t host_offset_; |
| 259 | }; |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 260 | static const int kMaxOffset = 1 << 29; |
| 261 | |
| 262 | explicit TypedSlotSet(Address page_start) : page_start_(page_start) { |
| 263 | chunk_ = new Chunk(nullptr, kInitialBufferSize); |
| 264 | } |
| 265 | |
| 266 | ~TypedSlotSet() { |
| 267 | Chunk* chunk = chunk_; |
| 268 | while (chunk != nullptr) { |
| 269 | Chunk* next = chunk->next; |
| 270 | delete chunk; |
| 271 | chunk = next; |
| 272 | } |
| 273 | } |
| 274 | |
| 275 | // The slot offset specifies a slot at address page_start_ + offset. |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame^] | 276 | void Insert(SlotType type, uint32_t host_offset, uint32_t offset) { |
| 277 | TypedSlot slot(type, host_offset, offset); |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 278 | if (!chunk_->AddSlot(slot)) { |
| 279 | chunk_ = new Chunk(chunk_, NextCapacity(chunk_->capacity)); |
| 280 | bool added = chunk_->AddSlot(slot); |
| 281 | DCHECK(added); |
| 282 | USE(added); |
| 283 | } |
| 284 | } |
| 285 | |
| 286 | // Iterate over all slots in the set and for each slot invoke the callback. |
| 287 | // If the callback returns REMOVE_SLOT then the slot is removed from the set. |
| 288 | // Returns the new number of slots. |
| 289 | // |
| 290 | // Sample usage: |
| 291 | // Iterate([](SlotType slot_type, Address slot_address) { |
| 292 | // if (good(slot_type, slot_address)) return KEEP_SLOT; |
| 293 | // else return REMOVE_SLOT; |
| 294 | // }); |
| 295 | template <typename Callback> |
| 296 | int Iterate(Callback callback) { |
| 297 | STATIC_ASSERT(NUMBER_OF_SLOT_TYPES < 8); |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame^] | 298 | const TypedSlot kRemovedSlot(NUMBER_OF_SLOT_TYPES, 0, 0); |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 299 | Chunk* chunk = chunk_; |
| 300 | int new_count = 0; |
| 301 | while (chunk != nullptr) { |
| 302 | TypedSlot* buffer = chunk->buffer; |
| 303 | int count = chunk->count; |
| 304 | for (int i = 0; i < count; i++) { |
| 305 | TypedSlot slot = buffer[i]; |
| 306 | if (slot != kRemovedSlot) { |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame^] | 307 | SlotType type = slot.type(); |
| 308 | Address addr = page_start_ + slot.offset(); |
| 309 | Address host_addr = page_start_ + slot.host_offset(); |
| 310 | if (callback(type, host_addr, addr) == KEEP_SLOT) { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 311 | new_count++; |
| 312 | } else { |
| 313 | buffer[i] = kRemovedSlot; |
| 314 | } |
| 315 | } |
| 316 | } |
| 317 | chunk = chunk->next; |
| 318 | } |
| 319 | return new_count; |
| 320 | } |
| 321 | |
| 322 | private: |
| 323 | static const int kInitialBufferSize = 100; |
| 324 | static const int kMaxBufferSize = 16 * KB; |
| 325 | |
| 326 | static int NextCapacity(int capacity) { |
| 327 | return Min(kMaxBufferSize, capacity * 2); |
| 328 | } |
| 329 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 330 | class OffsetField : public BitField<int, 0, 29> {}; |
| 331 | class TypeField : public BitField<SlotType, 29, 3> {}; |
| 332 | |
| 333 | struct Chunk : Malloced { |
| 334 | explicit Chunk(Chunk* next_chunk, int capacity) |
| 335 | : next(next_chunk), count(0), capacity(capacity) { |
| 336 | buffer = NewArray<TypedSlot>(capacity); |
| 337 | } |
| 338 | bool AddSlot(TypedSlot slot) { |
| 339 | if (count == capacity) return false; |
| 340 | buffer[count++] = slot; |
| 341 | return true; |
| 342 | } |
| 343 | ~Chunk() { DeleteArray(buffer); } |
| 344 | Chunk* next; |
| 345 | int count; |
| 346 | int capacity; |
| 347 | TypedSlot* buffer; |
| 348 | }; |
| 349 | |
| 350 | Address page_start_; |
| 351 | Chunk* chunk_; |
| 352 | }; |
| 353 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 354 | } // namespace internal |
| 355 | } // namespace v8 |
| 356 | |
| 357 | #endif // V8_SLOT_SET_H |