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
TEST(SlotSet,InsertAndLookup1)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
TEST(SlotSet,InsertAndLookup2)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
TEST(SlotSet,Iterate)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
TEST(SlotSet,Remove)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
CheckRemoveRangeOn(uint32_t start,uint32_t end)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
TEST(SlotSet,RemoveRange)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
TEST(TypedSlotSet,Iterate)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