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" |
| 10 | |
| 11 | namespace v8 { |
| 12 | namespace internal { |
| 13 | |
| 14 | // Data structure for maintaining a set of slots in a standard (non-large) |
| 15 | // page. The base address of the page must be set with SetPageStart before any |
| 16 | // operation. |
| 17 | // The data structure assumes that the slots are pointer size aligned and |
| 18 | // splits the valid slot offset range into kBuckets buckets. |
| 19 | // Each bucket is a bitmap with a bit corresponding to a single slot offset. |
| 20 | class SlotSet : public Malloced { |
| 21 | public: |
| 22 | enum CallbackResult { KEEP_SLOT, REMOVE_SLOT }; |
| 23 | |
| 24 | SlotSet() { |
| 25 | for (int i = 0; i < kBuckets; i++) { |
| 26 | bucket[i] = nullptr; |
| 27 | } |
| 28 | } |
| 29 | |
| 30 | ~SlotSet() { |
| 31 | for (int i = 0; i < kBuckets; i++) { |
| 32 | ReleaseBucket(i); |
| 33 | } |
| 34 | } |
| 35 | |
| 36 | void SetPageStart(Address page_start) { page_start_ = page_start; } |
| 37 | |
| 38 | // The slot offset specifies a slot at address page_start_ + slot_offset. |
| 39 | void Insert(int slot_offset) { |
| 40 | int bucket_index, cell_index, bit_index; |
| 41 | SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); |
| 42 | if (bucket[bucket_index] == nullptr) { |
| 43 | bucket[bucket_index] = AllocateBucket(); |
| 44 | } |
| 45 | bucket[bucket_index][cell_index] |= 1u << bit_index; |
| 46 | } |
| 47 | |
| 48 | // The slot offset specifies a slot at address page_start_ + slot_offset. |
| 49 | void Remove(int slot_offset) { |
| 50 | int bucket_index, cell_index, bit_index; |
| 51 | SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); |
| 52 | if (bucket[bucket_index] != nullptr) { |
| 53 | uint32_t cell = bucket[bucket_index][cell_index]; |
| 54 | if (cell) { |
| 55 | uint32_t bit_mask = 1u << bit_index; |
| 56 | if (cell & bit_mask) { |
| 57 | bucket[bucket_index][cell_index] ^= bit_mask; |
| 58 | } |
| 59 | } |
| 60 | } |
| 61 | } |
| 62 | |
| 63 | // The slot offsets specify a range of slots at addresses: |
| 64 | // [page_start_ + start_offset ... page_start_ + end_offset). |
| 65 | void RemoveRange(int start_offset, int end_offset) { |
| 66 | DCHECK_LE(start_offset, end_offset); |
| 67 | int start_bucket, start_cell, start_bit; |
| 68 | SlotToIndices(start_offset, &start_bucket, &start_cell, &start_bit); |
| 69 | int end_bucket, end_cell, end_bit; |
| 70 | SlotToIndices(end_offset, &end_bucket, &end_cell, &end_bit); |
| 71 | uint32_t start_mask = (1u << start_bit) - 1; |
| 72 | uint32_t end_mask = ~((1u << end_bit) - 1); |
| 73 | if (start_bucket == end_bucket && start_cell == end_cell) { |
| 74 | MaskCell(start_bucket, start_cell, start_mask | end_mask); |
| 75 | return; |
| 76 | } |
| 77 | int current_bucket = start_bucket; |
| 78 | int current_cell = start_cell; |
| 79 | MaskCell(current_bucket, current_cell, start_mask); |
| 80 | current_cell++; |
| 81 | if (current_bucket < end_bucket) { |
| 82 | if (bucket[current_bucket] != nullptr) { |
| 83 | while (current_cell < kCellsPerBucket) { |
| 84 | bucket[current_bucket][current_cell] = 0; |
| 85 | current_cell++; |
| 86 | } |
| 87 | } |
| 88 | // The rest of the current bucket is cleared. |
| 89 | // Move on to the next bucket. |
| 90 | current_bucket++; |
| 91 | current_cell = 0; |
| 92 | } |
| 93 | DCHECK(current_bucket == end_bucket || |
| 94 | (current_bucket < end_bucket && current_cell == 0)); |
| 95 | while (current_bucket < end_bucket) { |
| 96 | ReleaseBucket(current_bucket); |
| 97 | current_bucket++; |
| 98 | } |
| 99 | // All buckets between start_bucket and end_bucket are cleared. |
| 100 | DCHECK(current_bucket == end_bucket && current_cell <= end_cell); |
| 101 | if (current_bucket == kBuckets || bucket[current_bucket] == nullptr) { |
| 102 | return; |
| 103 | } |
| 104 | while (current_cell < end_cell) { |
| 105 | bucket[current_bucket][current_cell] = 0; |
| 106 | current_cell++; |
| 107 | } |
| 108 | // All cells between start_cell and end_cell are cleared. |
| 109 | DCHECK(current_bucket == end_bucket && current_cell == end_cell); |
| 110 | MaskCell(end_bucket, end_cell, end_mask); |
| 111 | } |
| 112 | |
| 113 | // The slot offset specifies a slot at address page_start_ + slot_offset. |
| 114 | bool Lookup(int slot_offset) { |
| 115 | int bucket_index, cell_index, bit_index; |
| 116 | SlotToIndices(slot_offset, &bucket_index, &cell_index, &bit_index); |
| 117 | if (bucket[bucket_index] != nullptr) { |
| 118 | uint32_t cell = bucket[bucket_index][cell_index]; |
| 119 | return (cell & (1u << bit_index)) != 0; |
| 120 | } |
| 121 | return false; |
| 122 | } |
| 123 | |
| 124 | // Iterate over all slots in the set and for each slot invoke the callback. |
| 125 | // If the callback returns REMOVE_SLOT then the slot is removed from the set. |
| 126 | // Returns the new number of slots. |
| 127 | // |
| 128 | // Sample usage: |
| 129 | // Iterate([](Address slot_address) { |
| 130 | // if (good(slot_address)) return KEEP_SLOT; |
| 131 | // else return REMOVE_SLOT; |
| 132 | // }); |
| 133 | template <typename Callback> |
| 134 | int Iterate(Callback callback) { |
| 135 | int new_count = 0; |
| 136 | for (int bucket_index = 0; bucket_index < kBuckets; bucket_index++) { |
| 137 | if (bucket[bucket_index] != nullptr) { |
| 138 | int in_bucket_count = 0; |
| 139 | uint32_t* current_bucket = bucket[bucket_index]; |
| 140 | int cell_offset = bucket_index * kBitsPerBucket; |
| 141 | for (int i = 0; i < kCellsPerBucket; i++, cell_offset += kBitsPerCell) { |
| 142 | if (current_bucket[i]) { |
| 143 | uint32_t cell = current_bucket[i]; |
| 144 | uint32_t old_cell = cell; |
| 145 | uint32_t new_cell = cell; |
| 146 | while (cell) { |
| 147 | int bit_offset = base::bits::CountTrailingZeros32(cell); |
| 148 | uint32_t bit_mask = 1u << bit_offset; |
| 149 | uint32_t slot = (cell_offset + bit_offset) << kPointerSizeLog2; |
| 150 | if (callback(page_start_ + slot) == KEEP_SLOT) { |
| 151 | ++in_bucket_count; |
| 152 | } else { |
| 153 | new_cell ^= bit_mask; |
| 154 | } |
| 155 | cell ^= bit_mask; |
| 156 | } |
| 157 | if (old_cell != new_cell) { |
| 158 | current_bucket[i] = new_cell; |
| 159 | } |
| 160 | } |
| 161 | } |
| 162 | if (in_bucket_count == 0) { |
| 163 | ReleaseBucket(bucket_index); |
| 164 | } |
| 165 | new_count += in_bucket_count; |
| 166 | } |
| 167 | } |
| 168 | return new_count; |
| 169 | } |
| 170 | |
| 171 | private: |
| 172 | static const int kMaxSlots = (1 << kPageSizeBits) / kPointerSize; |
| 173 | static const int kCellsPerBucket = 32; |
| 174 | static const int kCellsPerBucketLog2 = 5; |
| 175 | static const int kBitsPerCell = 32; |
| 176 | static const int kBitsPerCellLog2 = 5; |
| 177 | static const int kBitsPerBucket = kCellsPerBucket * kBitsPerCell; |
| 178 | static const int kBitsPerBucketLog2 = kCellsPerBucketLog2 + kBitsPerCellLog2; |
| 179 | static const int kBuckets = kMaxSlots / kCellsPerBucket / kBitsPerCell; |
| 180 | |
| 181 | uint32_t* AllocateBucket() { |
| 182 | uint32_t* result = NewArray<uint32_t>(kCellsPerBucket); |
| 183 | for (int i = 0; i < kCellsPerBucket; i++) { |
| 184 | result[i] = 0; |
| 185 | } |
| 186 | return result; |
| 187 | } |
| 188 | |
| 189 | void ReleaseBucket(int bucket_index) { |
| 190 | DeleteArray<uint32_t>(bucket[bucket_index]); |
| 191 | bucket[bucket_index] = nullptr; |
| 192 | } |
| 193 | |
| 194 | void MaskCell(int bucket_index, int cell_index, uint32_t mask) { |
| 195 | uint32_t* cells = bucket[bucket_index]; |
| 196 | if (cells != nullptr && cells[cell_index] != 0) { |
| 197 | cells[cell_index] &= mask; |
| 198 | } |
| 199 | } |
| 200 | |
| 201 | // Converts the slot offset into bucket/cell/bit index. |
| 202 | void SlotToIndices(int slot_offset, int* bucket_index, int* cell_index, |
| 203 | int* bit_index) { |
| 204 | DCHECK_EQ(slot_offset % kPointerSize, 0); |
| 205 | int slot = slot_offset >> kPointerSizeLog2; |
| 206 | DCHECK(slot >= 0 && slot <= kMaxSlots); |
| 207 | *bucket_index = slot >> kBitsPerBucketLog2; |
| 208 | *cell_index = (slot >> kBitsPerCellLog2) & (kCellsPerBucket - 1); |
| 209 | *bit_index = slot & (kBitsPerCell - 1); |
| 210 | } |
| 211 | |
| 212 | uint32_t* bucket[kBuckets]; |
| 213 | Address page_start_; |
| 214 | }; |
| 215 | |
| 216 | } // namespace internal |
| 217 | } // namespace v8 |
| 218 | |
| 219 | #endif // V8_SLOT_SET_H |