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 | #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) { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 58 | return KEEP_SLOT; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 59 | } else { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 60 | return REMOVE_SLOT; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 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 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 142 | TEST(TypedSlotSet, Iterate) { |
| 143 | TypedSlotSet set(0); |
| 144 | const int kDelta = 10000001; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 145 | const int kHostDelta = 50001; |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 146 | int added = 0; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 147 | uint32_t j = 0; |
| 148 | for (uint32_t i = 0; i < TypedSlotSet::kMaxOffset; |
| 149 | i += kDelta, j += kHostDelta) { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 150 | SlotType type = static_cast<SlotType>(i % NUMBER_OF_SLOT_TYPES); |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 151 | set.Insert(type, j, i); |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 152 | ++added; |
| 153 | } |
| 154 | int iterated = 0; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 155 | set.Iterate([&iterated, kDelta, kHostDelta](SlotType type, Address host_addr, |
| 156 | Address addr) { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 157 | uint32_t i = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(addr)); |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 158 | uint32_t j = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(host_addr)); |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 159 | EXPECT_EQ(i % NUMBER_OF_SLOT_TYPES, static_cast<uint32_t>(type)); |
| 160 | EXPECT_EQ(0, i % kDelta); |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 161 | EXPECT_EQ(0, j % kHostDelta); |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 162 | ++iterated; |
| 163 | return i % 2 == 0 ? KEEP_SLOT : REMOVE_SLOT; |
| 164 | }); |
| 165 | EXPECT_EQ(added, iterated); |
| 166 | iterated = 0; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 167 | set.Iterate([&iterated](SlotType type, Address host_addr, Address addr) { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 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 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 176 | } // namespace internal |
| 177 | } // namespace v8 |