| // Copyright 2016 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include <limits> |
| |
| #include "src/globals.h" |
| #include "src/heap/slot-set.h" |
| #include "src/heap/spaces.h" |
| #include "testing/gtest/include/gtest/gtest.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| TEST(SlotSet, InsertAndLookup1) { |
| SlotSet set; |
| set.SetPageStart(0); |
| for (int i = 0; i < Page::kPageSize; i += kPointerSize) { |
| EXPECT_FALSE(set.Lookup(i)); |
| } |
| for (int i = 0; i < Page::kPageSize; i += kPointerSize) { |
| set.Insert(i); |
| } |
| for (int i = 0; i < Page::kPageSize; i += kPointerSize) { |
| EXPECT_TRUE(set.Lookup(i)); |
| } |
| } |
| |
| TEST(SlotSet, InsertAndLookup2) { |
| SlotSet set; |
| set.SetPageStart(0); |
| for (int i = 0; i < Page::kPageSize; i += kPointerSize) { |
| if (i % 7 == 0) { |
| set.Insert(i); |
| } |
| } |
| for (int i = 0; i < Page::kPageSize; i += kPointerSize) { |
| if (i % 7 == 0) { |
| EXPECT_TRUE(set.Lookup(i)); |
| } else { |
| EXPECT_FALSE(set.Lookup(i)); |
| } |
| } |
| } |
| |
| TEST(SlotSet, Iterate) { |
| SlotSet set; |
| set.SetPageStart(0); |
| for (int i = 0; i < Page::kPageSize; i += kPointerSize) { |
| if (i % 7 == 0) { |
| set.Insert(i); |
| } |
| } |
| |
| set.Iterate([](Address slot_address) { |
| uintptr_t intaddr = reinterpret_cast<uintptr_t>(slot_address); |
| if (intaddr % 3 == 0) { |
| return KEEP_SLOT; |
| } else { |
| return REMOVE_SLOT; |
| } |
| }); |
| |
| for (int i = 0; i < Page::kPageSize; i += kPointerSize) { |
| if (i % 21 == 0) { |
| EXPECT_TRUE(set.Lookup(i)); |
| } else { |
| EXPECT_FALSE(set.Lookup(i)); |
| } |
| } |
| } |
| |
| TEST(SlotSet, Remove) { |
| SlotSet set; |
| set.SetPageStart(0); |
| for (int i = 0; i < Page::kPageSize; i += kPointerSize) { |
| if (i % 7 == 0) { |
| set.Insert(i); |
| } |
| } |
| |
| for (int i = 0; i < Page::kPageSize; i += kPointerSize) { |
| if (i % 3 != 0) { |
| set.Remove(i); |
| } |
| } |
| |
| for (int i = 0; i < Page::kPageSize; i += kPointerSize) { |
| if (i % 21 == 0) { |
| EXPECT_TRUE(set.Lookup(i)); |
| } else { |
| EXPECT_FALSE(set.Lookup(i)); |
| } |
| } |
| } |
| |
| void CheckRemoveRangeOn(uint32_t start, uint32_t end) { |
| SlotSet set; |
| set.SetPageStart(0); |
| uint32_t first = start == 0 ? 0 : start - kPointerSize; |
| uint32_t last = end == Page::kPageSize ? end - kPointerSize : end; |
| for (uint32_t i = first; i <= last; i += kPointerSize) { |
| set.Insert(i); |
| } |
| set.RemoveRange(start, end); |
| if (first != start) { |
| EXPECT_TRUE(set.Lookup(first)); |
| } |
| if (last == end) { |
| EXPECT_TRUE(set.Lookup(last)); |
| } |
| for (uint32_t i = start; i < end; i += kPointerSize) { |
| EXPECT_FALSE(set.Lookup(i)); |
| } |
| } |
| |
| TEST(SlotSet, RemoveRange) { |
| CheckRemoveRangeOn(0, Page::kPageSize); |
| CheckRemoveRangeOn(1 * kPointerSize, 1023 * kPointerSize); |
| for (uint32_t start = 0; start <= 32; start++) { |
| CheckRemoveRangeOn(start * kPointerSize, (start + 1) * kPointerSize); |
| CheckRemoveRangeOn(start * kPointerSize, (start + 2) * kPointerSize); |
| const uint32_t kEnds[] = {32, 64, 100, 128, 1024, 1500, 2048}; |
| for (int i = 0; i < sizeof(kEnds) / sizeof(uint32_t); i++) { |
| for (int k = -3; k <= 3; k++) { |
| uint32_t end = (kEnds[i] + k); |
| if (start < end) { |
| CheckRemoveRangeOn(start * kPointerSize, end * kPointerSize); |
| } |
| } |
| } |
| } |
| SlotSet set; |
| set.SetPageStart(0); |
| set.Insert(Page::kPageSize / 2); |
| set.RemoveRange(0, Page::kPageSize); |
| for (uint32_t i = 0; i < Page::kPageSize; i += kPointerSize) { |
| EXPECT_FALSE(set.Lookup(i)); |
| } |
| } |
| |
| TEST(TypedSlotSet, Iterate) { |
| TypedSlotSet set(0); |
| const int kDelta = 10000001; |
| int added = 0; |
| for (uint32_t i = 0; i < TypedSlotSet::kMaxOffset; i += kDelta) { |
| SlotType type = static_cast<SlotType>(i % NUMBER_OF_SLOT_TYPES); |
| set.Insert(type, i); |
| ++added; |
| } |
| int iterated = 0; |
| set.Iterate([&iterated, kDelta](SlotType type, Address addr) { |
| uint32_t i = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(addr)); |
| EXPECT_EQ(i % NUMBER_OF_SLOT_TYPES, static_cast<uint32_t>(type)); |
| EXPECT_EQ(0, i % kDelta); |
| ++iterated; |
| return i % 2 == 0 ? KEEP_SLOT : REMOVE_SLOT; |
| }); |
| EXPECT_EQ(added, iterated); |
| iterated = 0; |
| set.Iterate([&iterated](SlotType type, Address addr) { |
| uint32_t i = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(addr)); |
| EXPECT_EQ(0, i % 2); |
| ++iterated; |
| return KEEP_SLOT; |
| }); |
| EXPECT_EQ(added / 2, iterated); |
| } |
| |
| } // namespace internal |
| } // namespace v8 |