1 // Copyright 2020 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 "src/heap/cppgc/object-start-bitmap.h"
6
7 #include "include/cppgc/allocation.h"
8 #include "src/base/macros.h"
9 #include "src/heap/cppgc/globals.h"
10 #include "src/heap/cppgc/heap-object-header.h"
11 #include "src/heap/cppgc/page-memory.h"
12 #include "src/heap/cppgc/raw-heap.h"
13 #include "test/unittests/heap/cppgc/tests.h"
14 #include "testing/gtest/include/gtest/gtest.h"
15
16 namespace cppgc {
17 namespace internal {
18
19 namespace {
20
IsEmpty(const ObjectStartBitmap & bitmap)21 bool IsEmpty(const ObjectStartBitmap& bitmap) {
22 size_t count = 0;
23 bitmap.Iterate([&count](Address) { count++; });
24 return count == 0;
25 }
26
27 // Abstraction for objects that hides ObjectStartBitmap::kGranularity and
28 // the base address as getting either of it wrong will result in failed DCHECKs.
29 class Object {
30 public:
31 static Address kBaseOffset;
32
Object(size_t number)33 explicit Object(size_t number) : number_(number) {
34 const size_t max_entries = ObjectStartBitmap::MaxEntries();
35 EXPECT_GE(max_entries, number_);
36 }
37
address() const38 Address address() const {
39 return kBaseOffset + ObjectStartBitmap::Granularity() * number_;
40 }
41
header() const42 HeapObjectHeader* header() const {
43 return reinterpret_cast<HeapObjectHeader*>(address());
44 }
45
46 // Allow implicitly converting Object to Address.
operator Address() const47 operator Address() const { return address(); }
48
49 private:
50 const size_t number_;
51 };
52
53 Address Object::kBaseOffset = reinterpret_cast<Address>(0x4000);
54
55 } // namespace
56
TEST(ObjectStartBitmapTest,MoreThanZeroEntriesPossible)57 TEST(ObjectStartBitmapTest, MoreThanZeroEntriesPossible) {
58 const size_t max_entries = ObjectStartBitmap::MaxEntries();
59 EXPECT_LT(0u, max_entries);
60 }
61
TEST(ObjectStartBitmapTest,InitialEmpty)62 TEST(ObjectStartBitmapTest, InitialEmpty) {
63 ObjectStartBitmap bitmap(Object::kBaseOffset);
64 EXPECT_TRUE(IsEmpty(bitmap));
65 }
66
TEST(ObjectStartBitmapTest,SetBitImpliesNonEmpty)67 TEST(ObjectStartBitmapTest, SetBitImpliesNonEmpty) {
68 ObjectStartBitmap bitmap(Object::kBaseOffset);
69 bitmap.SetBit(Object(0));
70 EXPECT_FALSE(IsEmpty(bitmap));
71 }
72
TEST(ObjectStartBitmapTest,SetBitCheckBit)73 TEST(ObjectStartBitmapTest, SetBitCheckBit) {
74 ObjectStartBitmap bitmap(Object::kBaseOffset);
75 Object object(7);
76 bitmap.SetBit(object);
77 EXPECT_TRUE(bitmap.CheckBit(object));
78 }
79
TEST(ObjectStartBitmapTest,SetBitClearbitCheckBit)80 TEST(ObjectStartBitmapTest, SetBitClearbitCheckBit) {
81 ObjectStartBitmap bitmap(Object::kBaseOffset);
82 Object object(77);
83 bitmap.SetBit(object);
84 bitmap.ClearBit(object);
85 EXPECT_FALSE(bitmap.CheckBit(object));
86 }
87
TEST(ObjectStartBitmapTest,SetBitClearBitImpliesEmpty)88 TEST(ObjectStartBitmapTest, SetBitClearBitImpliesEmpty) {
89 ObjectStartBitmap bitmap(Object::kBaseOffset);
90 Object object(123);
91 bitmap.SetBit(object);
92 bitmap.ClearBit(object);
93 EXPECT_TRUE(IsEmpty(bitmap));
94 }
95
TEST(ObjectStartBitmapTest,AdjacentObjectsAtBegin)96 TEST(ObjectStartBitmapTest, AdjacentObjectsAtBegin) {
97 ObjectStartBitmap bitmap(Object::kBaseOffset);
98 Object object0(0);
99 Object object1(1);
100 bitmap.SetBit(object0);
101 bitmap.SetBit(object1);
102 EXPECT_FALSE(bitmap.CheckBit(Object(3)));
103 size_t count = 0;
104 bitmap.Iterate([&count, object0, object1](Address current) {
105 if (count == 0) {
106 EXPECT_EQ(object0.address(), current);
107 } else if (count == 1) {
108 EXPECT_EQ(object1.address(), current);
109 }
110 count++;
111 });
112 EXPECT_EQ(2u, count);
113 }
114
TEST(ObjectStartBitmapTest,AdjacentObjectsAtEnd)115 TEST(ObjectStartBitmapTest, AdjacentObjectsAtEnd) {
116 ObjectStartBitmap bitmap(Object::kBaseOffset);
117 const size_t last_entry_index = ObjectStartBitmap::MaxEntries() - 1;
118 Object object0(last_entry_index - 1);
119 Object object1(last_entry_index);
120 bitmap.SetBit(object0);
121 bitmap.SetBit(object1);
122 EXPECT_FALSE(bitmap.CheckBit(Object(last_entry_index - 2)));
123 size_t count = 0;
124 bitmap.Iterate([&count, object0, object1](Address current) {
125 if (count == 0) {
126 EXPECT_EQ(object0.address(), current);
127 } else if (count == 1) {
128 EXPECT_EQ(object1.address(), current);
129 }
130 count++;
131 });
132 EXPECT_EQ(2u, count);
133 }
134
TEST(ObjectStartBitmapTest,FindHeaderExact)135 TEST(ObjectStartBitmapTest, FindHeaderExact) {
136 ObjectStartBitmap bitmap(Object::kBaseOffset);
137 Object object(654);
138 bitmap.SetBit(object);
139 EXPECT_EQ(object.header(), bitmap.FindHeader(object.address()));
140 }
141
TEST(ObjectStartBitmapTest,FindHeaderApproximate)142 TEST(ObjectStartBitmapTest, FindHeaderApproximate) {
143 static const size_t kInternalDelta = 37;
144 ObjectStartBitmap bitmap(Object::kBaseOffset);
145 Object object(654);
146 bitmap.SetBit(object);
147 EXPECT_EQ(object.header(),
148 bitmap.FindHeader(object.address() + kInternalDelta));
149 }
150
TEST(ObjectStartBitmapTest,FindHeaderIteratingWholeBitmap)151 TEST(ObjectStartBitmapTest, FindHeaderIteratingWholeBitmap) {
152 ObjectStartBitmap bitmap(Object::kBaseOffset);
153 Object object_to_find(Object(0));
154 Address hint_index = Object(ObjectStartBitmap::MaxEntries() - 1);
155 bitmap.SetBit(object_to_find);
156 EXPECT_EQ(object_to_find.header(), bitmap.FindHeader(hint_index));
157 }
158
TEST(ObjectStartBitmapTest,FindHeaderNextCell)159 TEST(ObjectStartBitmapTest, FindHeaderNextCell) {
160 // This white box test makes use of the fact that cells are of type uint8_t.
161 const size_t kCellSize = sizeof(uint8_t);
162 ObjectStartBitmap bitmap(Object::kBaseOffset);
163 Object object_to_find(Object(kCellSize - 1));
164 Address hint = Object(kCellSize);
165 bitmap.SetBit(Object(0));
166 bitmap.SetBit(object_to_find);
167 EXPECT_EQ(object_to_find.header(), bitmap.FindHeader(hint));
168 }
169
TEST(ObjectStartBitmapTest,FindHeaderSameCell)170 TEST(ObjectStartBitmapTest, FindHeaderSameCell) {
171 // This white box test makes use of the fact that cells are of type uint8_t.
172 const size_t kCellSize = sizeof(uint8_t);
173 ObjectStartBitmap bitmap(Object::kBaseOffset);
174 Object object_to_find(Object(kCellSize - 1));
175 bitmap.SetBit(Object(0));
176 bitmap.SetBit(object_to_find);
177 EXPECT_EQ(object_to_find.header(),
178 bitmap.FindHeader(object_to_find.address()));
179 }
180
181 } // namespace internal
182 } // namespace cppgc
183