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 #include <limits> 6 7 #include "src/globals.h" 8 #include "src/heap/slot-set.h" 9 #include "src/heap/spaces.h" 10 #include "testing/gtest/include/gtest/gtest.h" 11 12 namespace v8 { 13 namespace internal { 14 15 TEST(SlotSet, InsertAndLookup1) { 16 SlotSet set; 17 set.SetPageStart(0); 18 for (int i = 0; i < Page::kPageSize; i += kPointerSize) { 19 EXPECT_FALSE(set.Lookup(i)); 20 } 21 for (int i = 0; i < Page::kPageSize; i += kPointerSize) { 22 set.Insert(i); 23 } 24 for (int i = 0; i < Page::kPageSize; i += kPointerSize) { 25 EXPECT_TRUE(set.Lookup(i)); 26 } 27 } 28 29 TEST(SlotSet, InsertAndLookup2) { 30 SlotSet set; 31 set.SetPageStart(0); 32 for (int i = 0; i < Page::kPageSize; i += kPointerSize) { 33 if (i % 7 == 0) { 34 set.Insert(i); 35 } 36 } 37 for (int i = 0; i < Page::kPageSize; i += kPointerSize) { 38 if (i % 7 == 0) { 39 EXPECT_TRUE(set.Lookup(i)); 40 } else { 41 EXPECT_FALSE(set.Lookup(i)); 42 } 43 } 44 } 45 46 TEST(SlotSet, Iterate) { 47 SlotSet set; 48 set.SetPageStart(0); 49 for (int i = 0; i < Page::kPageSize; i += kPointerSize) { 50 if (i % 7 == 0) { 51 set.Insert(i); 52 } 53 } 54 55 set.Iterate([](Address slot_address) { 56 uintptr_t intaddr = reinterpret_cast<uintptr_t>(slot_address); 57 if (intaddr % 3 == 0) { 58 return KEEP_SLOT; 59 } else { 60 return REMOVE_SLOT; 61 } 62 }); 63 64 for (int i = 0; i < Page::kPageSize; i += kPointerSize) { 65 if (i % 21 == 0) { 66 EXPECT_TRUE(set.Lookup(i)); 67 } else { 68 EXPECT_FALSE(set.Lookup(i)); 69 } 70 } 71 } 72 73 TEST(SlotSet, Remove) { 74 SlotSet set; 75 set.SetPageStart(0); 76 for (int i = 0; i < Page::kPageSize; i += kPointerSize) { 77 if (i % 7 == 0) { 78 set.Insert(i); 79 } 80 } 81 82 for (int i = 0; i < Page::kPageSize; i += kPointerSize) { 83 if (i % 3 != 0) { 84 set.Remove(i); 85 } 86 } 87 88 for (int i = 0; i < Page::kPageSize; i += kPointerSize) { 89 if (i % 21 == 0) { 90 EXPECT_TRUE(set.Lookup(i)); 91 } else { 92 EXPECT_FALSE(set.Lookup(i)); 93 } 94 } 95 } 96 97 void CheckRemoveRangeOn(uint32_t start, uint32_t end) { 98 SlotSet set; 99 set.SetPageStart(0); 100 uint32_t first = start == 0 ? 0 : start - kPointerSize; 101 uint32_t last = end == Page::kPageSize ? end - kPointerSize : end; 102 for (uint32_t i = first; i <= last; i += kPointerSize) { 103 set.Insert(i); 104 } 105 set.RemoveRange(start, end); 106 if (first != start) { 107 EXPECT_TRUE(set.Lookup(first)); 108 } 109 if (last == end) { 110 EXPECT_TRUE(set.Lookup(last)); 111 } 112 for (uint32_t i = start; i < end; i += kPointerSize) { 113 EXPECT_FALSE(set.Lookup(i)); 114 } 115 } 116 117 TEST(SlotSet, RemoveRange) { 118 CheckRemoveRangeOn(0, Page::kPageSize); 119 CheckRemoveRangeOn(1 * kPointerSize, 1023 * kPointerSize); 120 for (uint32_t start = 0; start <= 32; start++) { 121 CheckRemoveRangeOn(start * kPointerSize, (start + 1) * kPointerSize); 122 CheckRemoveRangeOn(start * kPointerSize, (start + 2) * kPointerSize); 123 const uint32_t kEnds[] = {32, 64, 100, 128, 1024, 1500, 2048}; 124 for (int i = 0; i < sizeof(kEnds) / sizeof(uint32_t); i++) { 125 for (int k = -3; k <= 3; k++) { 126 uint32_t end = (kEnds[i] + k); 127 if (start < end) { 128 CheckRemoveRangeOn(start * kPointerSize, end * kPointerSize); 129 } 130 } 131 } 132 } 133 SlotSet set; 134 set.SetPageStart(0); 135 set.Insert(Page::kPageSize / 2); 136 set.RemoveRange(0, Page::kPageSize); 137 for (uint32_t i = 0; i < Page::kPageSize; i += kPointerSize) { 138 EXPECT_FALSE(set.Lookup(i)); 139 } 140 } 141 142 TEST(TypedSlotSet, Iterate) { 143 TypedSlotSet set(0); 144 const int kDelta = 10000001; 145 const int kHostDelta = 50001; 146 int added = 0; 147 uint32_t j = 0; 148 for (uint32_t i = 0; i < TypedSlotSet::kMaxOffset; 149 i += kDelta, j += kHostDelta) { 150 SlotType type = static_cast<SlotType>(i % NUMBER_OF_SLOT_TYPES); 151 set.Insert(type, j, i); 152 ++added; 153 } 154 int iterated = 0; 155 set.Iterate([&iterated, kDelta, kHostDelta](SlotType type, Address host_addr, 156 Address addr) { 157 uint32_t i = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(addr)); 158 uint32_t j = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(host_addr)); 159 EXPECT_EQ(i % NUMBER_OF_SLOT_TYPES, static_cast<uint32_t>(type)); 160 EXPECT_EQ(0, i % kDelta); 161 EXPECT_EQ(0, j % kHostDelta); 162 ++iterated; 163 return i % 2 == 0 ? KEEP_SLOT : REMOVE_SLOT; 164 }); 165 EXPECT_EQ(added, iterated); 166 iterated = 0; 167 set.Iterate([&iterated](SlotType type, Address host_addr, Address addr) { 168 uint32_t i = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(addr)); 169 EXPECT_EQ(0, i % 2); 170 ++iterated; 171 return KEEP_SLOT; 172 }); 173 EXPECT_EQ(added / 2, iterated); 174 } 175 176 } // namespace internal 177 } // namespace v8 178
