Line data Source code
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 : #include <map>
7 :
8 : #include "src/globals.h"
9 : #include "src/heap/slot-set.h"
10 : #include "src/heap/spaces.h"
11 : #include "src/objects/slots.h"
12 : #include "testing/gtest/include/gtest/gtest.h"
13 :
14 : namespace v8 {
15 : namespace internal {
16 :
17 15443 : TEST(SlotSet, InsertAndLookup1) {
18 2 : SlotSet set;
19 : set.SetPageStart(0);
20 65537 : for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
21 65536 : EXPECT_FALSE(set.Lookup(i));
22 : }
23 65537 : for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
24 32768 : set.Insert(i);
25 : }
26 65537 : for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
27 65536 : EXPECT_TRUE(set.Lookup(i));
28 : }
29 1 : }
30 :
31 15443 : TEST(SlotSet, InsertAndLookup2) {
32 2 : SlotSet set;
33 : set.SetPageStart(0);
34 65537 : for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
35 32768 : if (i % 7 == 0) {
36 4682 : set.Insert(i);
37 : }
38 : }
39 65537 : for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
40 32768 : if (i % 7 == 0) {
41 9364 : EXPECT_TRUE(set.Lookup(i));
42 : } else {
43 56172 : EXPECT_FALSE(set.Lookup(i));
44 : }
45 : }
46 1 : }
47 :
48 15443 : TEST(SlotSet, Iterate) {
49 2 : SlotSet set;
50 : set.SetPageStart(0);
51 65537 : for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
52 32768 : if (i % 7 == 0) {
53 4682 : set.Insert(i);
54 : }
55 : }
56 :
57 : set.Iterate(
58 : [](MaybeObjectSlot slot) {
59 4682 : if (slot.address() % 3 == 0) {
60 : return KEEP_SLOT;
61 : } else {
62 : return REMOVE_SLOT;
63 : }
64 : },
65 1 : SlotSet::KEEP_EMPTY_BUCKETS);
66 :
67 65537 : for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
68 32768 : if (i % 21 == 0) {
69 3122 : EXPECT_TRUE(set.Lookup(i));
70 : } else {
71 62414 : EXPECT_FALSE(set.Lookup(i));
72 : }
73 : }
74 1 : }
75 :
76 15443 : TEST(SlotSet, Remove) {
77 2 : SlotSet set;
78 : set.SetPageStart(0);
79 65537 : for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
80 32768 : if (i % 7 == 0) {
81 4682 : set.Insert(i);
82 : }
83 : }
84 :
85 65537 : for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
86 32768 : if (i % 3 != 0) {
87 21845 : set.Remove(i);
88 : }
89 : }
90 :
91 65537 : for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
92 32768 : if (i % 21 == 0) {
93 3122 : EXPECT_TRUE(set.Lookup(i));
94 : } else {
95 62414 : EXPECT_FALSE(set.Lookup(i));
96 : }
97 : }
98 1 : }
99 :
100 1675 : void CheckRemoveRangeOn(uint32_t start, uint32_t end) {
101 3350 : SlotSet set;
102 : set.SetPageStart(0);
103 1675 : uint32_t first = start == 0 ? 0 : start - kTaggedSize;
104 1675 : uint32_t last = end == Page::kPageSize ? end - kTaggedSize : end;
105 8375 : for (const auto mode :
106 3350 : {SlotSet::FREE_EMPTY_BUCKETS, SlotSet::KEEP_EMPTY_BUCKETS}) {
107 4572550 : for (uint32_t i = first; i <= last; i += kTaggedSize) {
108 2284600 : set.Insert(i);
109 : }
110 3350 : set.RemoveRange(start, end, mode);
111 3350 : if (first != start) {
112 6492 : EXPECT_TRUE(set.Lookup(first));
113 : }
114 3350 : if (last == end) {
115 6696 : EXPECT_TRUE(set.Lookup(last));
116 : }
117 4559362 : for (uint32_t i = start; i < end; i += kTaggedSize) {
118 4556012 : EXPECT_FALSE(set.Lookup(i));
119 : }
120 : }
121 1675 : }
122 :
123 15443 : TEST(SlotSet, RemoveRange) {
124 1 : CheckRemoveRangeOn(0, Page::kPageSize);
125 1 : CheckRemoveRangeOn(1 * kTaggedSize, 1023 * kTaggedSize);
126 67 : for (uint32_t start = 0; start <= 32; start++) {
127 33 : CheckRemoveRangeOn(start * kTaggedSize, (start + 1) * kTaggedSize);
128 33 : CheckRemoveRangeOn(start * kTaggedSize, (start + 2) * kTaggedSize);
129 33 : const uint32_t kEnds[] = {32, 64, 100, 128, 1024, 1500, 2048};
130 495 : for (size_t i = 0; i < sizeof(kEnds) / sizeof(uint32_t); i++) {
131 3465 : for (int k = -3; k <= 3; k++) {
132 1617 : uint32_t end = (kEnds[i] + k);
133 1617 : if (start < end) {
134 1607 : CheckRemoveRangeOn(start * kTaggedSize, end * kTaggedSize);
135 : }
136 : }
137 : }
138 : }
139 2 : SlotSet set;
140 : set.SetPageStart(0);
141 5 : for (const auto mode :
142 2 : {SlotSet::FREE_EMPTY_BUCKETS, SlotSet::KEEP_EMPTY_BUCKETS}) {
143 2 : set.Insert(Page::kPageSize / 2);
144 2 : set.RemoveRange(0, Page::kPageSize, mode);
145 131074 : for (uint32_t i = 0; i < Page::kPageSize; i += kTaggedSize) {
146 131072 : EXPECT_FALSE(set.Lookup(i));
147 : }
148 : }
149 1 : }
150 :
151 15443 : TEST(TypedSlotSet, Iterate) {
152 2 : TypedSlotSet set(0);
153 : // These two constants must be static as a workaround
154 : // for a MSVC++ bug about lambda captures, see the discussion at
155 : // https://social.msdn.microsoft.com/Forums/SqlServer/4abf18bd-4ae4-4c72-ba3e-3b13e7909d5f
156 : static const int kDelta = 10000001;
157 1 : int added = 0;
158 109 : for (uint32_t i = 0; i < TypedSlotSet::kMaxOffset; i += kDelta) {
159 54 : SlotType type = static_cast<SlotType>(i % CLEARED_SLOT);
160 54 : set.Insert(type, i);
161 54 : ++added;
162 : }
163 1 : int iterated = 0;
164 : set.Iterate(
165 108 : [&iterated](SlotType type, Address addr) {
166 54 : uint32_t i = static_cast<uint32_t>(addr);
167 108 : EXPECT_EQ(i % CLEARED_SLOT, static_cast<uint32_t>(type));
168 108 : EXPECT_EQ(0u, i % kDelta);
169 54 : ++iterated;
170 54 : return i % 2 == 0 ? KEEP_SLOT : REMOVE_SLOT;
171 : },
172 1 : TypedSlotSet::KEEP_EMPTY_CHUNKS);
173 1 : EXPECT_EQ(added, iterated);
174 1 : iterated = 0;
175 : set.Iterate(
176 54 : [&iterated](SlotType type, Address addr) {
177 27 : uint32_t i = static_cast<uint32_t>(addr);
178 54 : EXPECT_EQ(0u, i % 2);
179 27 : ++iterated;
180 27 : return KEEP_SLOT;
181 : },
182 1 : TypedSlotSet::KEEP_EMPTY_CHUNKS);
183 2 : EXPECT_EQ(added / 2, iterated);
184 1 : }
185 :
186 15443 : TEST(TypedSlotSet, ClearInvalidSlots) {
187 2 : TypedSlotSet set(0);
188 : const int kHostDelta = 100;
189 : uint32_t entries = 10;
190 21 : for (uint32_t i = 0; i < entries; i++) {
191 10 : SlotType type = static_cast<SlotType>(i % CLEARED_SLOT);
192 10 : set.Insert(type, i * kHostDelta);
193 : }
194 :
195 : std::map<uint32_t, uint32_t> invalid_ranges;
196 11 : for (uint32_t i = 1; i < entries; i += 2) {
197 : invalid_ranges.insert(
198 10 : std::pair<uint32_t, uint32_t>(i * kHostDelta, i * kHostDelta + 1));
199 : }
200 :
201 1 : set.ClearInvalidSlots(invalid_ranges);
202 6 : for (std::map<uint32_t, uint32_t>::iterator it = invalid_ranges.begin();
203 : it != invalid_ranges.end(); ++it) {
204 5 : uint32_t start = it->first;
205 5 : uint32_t end = it->second;
206 : set.Iterate(
207 : [=](SlotType slot_type, Address slot_addr) {
208 25 : CHECK(slot_addr < start || slot_addr >= end);
209 : return KEEP_SLOT;
210 : },
211 5 : TypedSlotSet::KEEP_EMPTY_CHUNKS);
212 : }
213 1 : }
214 :
215 15443 : TEST(TypedSlotSet, Merge) {
216 2 : TypedSlotSet set0(0), set1(0);
217 : static const uint32_t kEntries = 10000;
218 20001 : for (uint32_t i = 0; i < kEntries; i++) {
219 10000 : set0.Insert(EMBEDDED_OBJECT_SLOT, 2 * i);
220 10000 : set1.Insert(EMBEDDED_OBJECT_SLOT, 2 * i + 1);
221 : }
222 1 : uint32_t count = 0;
223 1 : set0.Merge(&set1);
224 : set0.Iterate(
225 20000 : [&count](SlotType slot_type, Address slot_addr) {
226 20000 : if (count < kEntries) {
227 20000 : CHECK_EQ(slot_addr % 2, 0);
228 : } else {
229 20000 : CHECK_EQ(slot_addr % 2, 1);
230 : }
231 20000 : ++count;
232 20000 : return KEEP_SLOT;
233 : },
234 1 : TypedSlotSet::KEEP_EMPTY_CHUNKS);
235 1 : CHECK_EQ(2 * kEntries, count);
236 : set1.Iterate(
237 0 : [](SlotType slot_type, Address slot_addr) {
238 0 : CHECK(false); // Unreachable.
239 : return KEEP_SLOT;
240 : },
241 1 : TypedSlotSet::KEEP_EMPTY_CHUNKS);
242 1 : }
243 :
244 : } // namespace internal
245 9264 : } // namespace v8
|
