1 /*
2  * Copyright (C) 2013 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include <memory>
18 #include <random>
19 
20 #include "allocator.h"
21 #include "base/stl_util.h"
22 #include "bit_vector-inl.h"
23 #include "gtest/gtest.h"
24 #include "transform_iterator.h"
25 
26 namespace art {
27 
TEST(BitVector,Test)28 TEST(BitVector, Test) {
29   const size_t kBits = 32;
30 
31   BitVector bv(kBits, false, Allocator::GetCallocAllocator());
32   EXPECT_EQ(1U, bv.GetStorageSize());
33   EXPECT_EQ(sizeof(uint32_t), bv.GetSizeOf());
34   EXPECT_FALSE(bv.IsExpandable());
35 
36   EXPECT_EQ(0U, bv.NumSetBits());
37   EXPECT_EQ(0U, bv.NumSetBits(1));
38   EXPECT_EQ(0U, bv.NumSetBits(kBits));
39   for (size_t i = 0; i < kBits; i++) {
40     EXPECT_FALSE(bv.IsBitSet(i));
41   }
42   EXPECT_EQ(0U, bv.GetRawStorageWord(0));
43   EXPECT_EQ(0U, *bv.GetRawStorage());
44 
45   EXPECT_TRUE(bv.Indexes().begin().Done());
46   EXPECT_TRUE(bv.Indexes().begin() == bv.Indexes().end());
47 
48   bv.SetBit(0);
49   bv.SetBit(kBits - 1);
50   EXPECT_EQ(2U, bv.NumSetBits());
51   EXPECT_EQ(1U, bv.NumSetBits(1));
52   EXPECT_EQ(2U, bv.NumSetBits(kBits));
53   EXPECT_TRUE(bv.IsBitSet(0));
54   for (size_t i = 1; i < kBits - 1; i++) {
55     EXPECT_FALSE(bv.IsBitSet(i));
56   }
57   EXPECT_TRUE(bv.IsBitSet(kBits - 1));
58   EXPECT_EQ(0x80000001U, bv.GetRawStorageWord(0));
59   EXPECT_EQ(0x80000001U, *bv.GetRawStorage());
60 
61   BitVector::IndexIterator iterator = bv.Indexes().begin();
62   EXPECT_TRUE(iterator != bv.Indexes().end());
63   EXPECT_EQ(0u, *iterator);
64   ++iterator;
65   EXPECT_TRUE(iterator != bv.Indexes().end());
66   EXPECT_EQ(kBits - 1u, *iterator);
67   ++iterator;
68   EXPECT_TRUE(iterator == bv.Indexes().end());
69 }
70 
71 struct MessyAllocator : public Allocator {
72  public:
MessyAllocatorart::MessyAllocator73   MessyAllocator() : malloc_(Allocator::GetCallocAllocator()) {}
~MessyAllocatorart::MessyAllocator74   ~MessyAllocator() {}
75 
Allocart::MessyAllocator76   void* Alloc(size_t s) override {
77     void* res = malloc_->Alloc(s);
78     memset(res, 0xfe, s);
79     return res;
80   }
81 
Freeart::MessyAllocator82   void Free(void* v) override {
83     malloc_->Free(v);
84   }
85 
86  private:
87   Allocator* malloc_;
88 };
89 
TEST(BitVector,MessyAllocator)90 TEST(BitVector, MessyAllocator) {
91   MessyAllocator alloc;
92   BitVector bv(32, false, &alloc);
93   bv.ClearAllBits();
94   EXPECT_EQ(bv.NumSetBits(), 0u);
95   EXPECT_EQ(bv.GetHighestBitSet(), -1);
96 }
97 
TEST(BitVector,NoopAllocator)98 TEST(BitVector, NoopAllocator) {
99   const uint32_t kWords = 2;
100 
101   uint32_t bits[kWords];
102   memset(bits, 0, sizeof(bits));
103 
104   BitVector bv(false, Allocator::GetNoopAllocator(), kWords, bits);
105   EXPECT_EQ(kWords, bv.GetStorageSize());
106   EXPECT_EQ(kWords * sizeof(uint32_t), bv.GetSizeOf());
107   EXPECT_EQ(bits, bv.GetRawStorage());
108   EXPECT_EQ(0U, bv.NumSetBits());
109 
110   bv.SetBit(8);
111   EXPECT_EQ(1U, bv.NumSetBits());
112   EXPECT_EQ(0x00000100U, bv.GetRawStorageWord(0));
113   EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1));
114   EXPECT_EQ(1U, bv.NumSetBits());
115 
116   bv.SetBit(16);
117   EXPECT_EQ(2U, bv.NumSetBits());
118   EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
119   EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1));
120   EXPECT_EQ(2U, bv.NumSetBits());
121 
122   bv.SetBit(32);
123   EXPECT_EQ(3U, bv.NumSetBits());
124   EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
125   EXPECT_EQ(0x00000001U, bv.GetRawStorageWord(1));
126   EXPECT_EQ(3U, bv.NumSetBits());
127 
128   bv.SetBit(48);
129   EXPECT_EQ(4U, bv.NumSetBits());
130   EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
131   EXPECT_EQ(0x00010001U, bv.GetRawStorageWord(1));
132   EXPECT_EQ(4U, bv.NumSetBits());
133 
134   EXPECT_EQ(0U, bv.NumSetBits(1));
135 
136   EXPECT_EQ(0U, bv.NumSetBits(8));
137   EXPECT_EQ(1U, bv.NumSetBits(9));
138   EXPECT_EQ(1U, bv.NumSetBits(10));
139 
140   EXPECT_EQ(1U, bv.NumSetBits(16));
141   EXPECT_EQ(2U, bv.NumSetBits(17));
142   EXPECT_EQ(2U, bv.NumSetBits(18));
143 
144   EXPECT_EQ(2U, bv.NumSetBits(32));
145   EXPECT_EQ(3U, bv.NumSetBits(33));
146   EXPECT_EQ(3U, bv.NumSetBits(34));
147 
148   EXPECT_EQ(3U, bv.NumSetBits(48));
149   EXPECT_EQ(4U, bv.NumSetBits(49));
150   EXPECT_EQ(4U, bv.NumSetBits(50));
151 
152   EXPECT_EQ(4U, bv.NumSetBits(64));
153 }
154 
TEST(BitVector,SetInitialBits)155 TEST(BitVector, SetInitialBits) {
156   const uint32_t kWords = 2;
157 
158   uint32_t bits[kWords];
159   memset(bits, 0, sizeof(bits));
160 
161   BitVector bv(false, Allocator::GetNoopAllocator(), kWords, bits);
162   bv.SetInitialBits(0u);
163   EXPECT_EQ(0u, bv.NumSetBits());
164   bv.SetInitialBits(1u);
165   EXPECT_EQ(1u, bv.NumSetBits());
166   bv.SetInitialBits(32u);
167   EXPECT_EQ(32u, bv.NumSetBits());
168   bv.SetInitialBits(63u);
169   EXPECT_EQ(63u, bv.NumSetBits());
170   bv.SetInitialBits(64u);
171   EXPECT_EQ(64u, bv.NumSetBits());
172 }
173 
TEST(BitVector,UnionIfNotIn)174 TEST(BitVector, UnionIfNotIn) {
175   {
176     BitVector first(2, true, Allocator::GetCallocAllocator());
177     BitVector second(5, true, Allocator::GetCallocAllocator());
178     BitVector third(5, true, Allocator::GetCallocAllocator());
179 
180     second.SetBit(64);
181     third.SetBit(64);
182     bool changed = first.UnionIfNotIn(&second, &third);
183     EXPECT_EQ(0u, first.NumSetBits());
184     EXPECT_FALSE(changed);
185   }
186 
187   {
188     BitVector first(2, true, Allocator::GetCallocAllocator());
189     BitVector second(5, true, Allocator::GetCallocAllocator());
190     BitVector third(5, true, Allocator::GetCallocAllocator());
191 
192     second.SetBit(64);
193     bool changed = first.UnionIfNotIn(&second, &third);
194     EXPECT_EQ(1u, first.NumSetBits());
195     EXPECT_TRUE(changed);
196     EXPECT_TRUE(first.IsBitSet(64));
197   }
198 }
199 
TEST(BitVector,Subset)200 TEST(BitVector, Subset) {
201   {
202     BitVector first(2, true, Allocator::GetCallocAllocator());
203     BitVector second(5, true, Allocator::GetCallocAllocator());
204 
205     EXPECT_TRUE(first.IsSubsetOf(&second));
206     second.SetBit(4);
207     EXPECT_TRUE(first.IsSubsetOf(&second));
208   }
209 
210   {
211     BitVector first(5, true, Allocator::GetCallocAllocator());
212     BitVector second(5, true, Allocator::GetCallocAllocator());
213 
214     first.SetBit(5);
215     EXPECT_FALSE(first.IsSubsetOf(&second));
216     second.SetBit(4);
217     EXPECT_FALSE(first.IsSubsetOf(&second));
218   }
219 
220   {
221     BitVector first(5, true, Allocator::GetCallocAllocator());
222     BitVector second(5, true, Allocator::GetCallocAllocator());
223 
224     first.SetBit(16);
225     first.SetBit(32);
226     first.SetBit(48);
227     second.SetBit(16);
228     second.SetBit(32);
229     second.SetBit(48);
230 
231     EXPECT_TRUE(first.IsSubsetOf(&second));
232     second.SetBit(8);
233     EXPECT_TRUE(first.IsSubsetOf(&second));
234     second.SetBit(40);
235     EXPECT_TRUE(first.IsSubsetOf(&second));
236     second.SetBit(52);
237     EXPECT_TRUE(first.IsSubsetOf(&second));
238 
239     first.SetBit(9);
240     EXPECT_FALSE(first.IsSubsetOf(&second));
241   }
242 }
243 
TEST(BitVector,CopyTo)244 TEST(BitVector, CopyTo) {
245   {
246     // Test copying an empty BitVector. Padding should fill `buf` with zeroes.
247     BitVector bv(0, true, Allocator::GetCallocAllocator());
248     uint32_t buf;
249 
250     bv.CopyTo(&buf, sizeof(buf));
251     EXPECT_EQ(0u, bv.GetSizeOf());
252     EXPECT_EQ(0u, buf);
253   }
254 
255   {
256     // Test copying when `bv.storage_` and `buf` are of equal lengths.
257     BitVector bv(0, true, Allocator::GetCallocAllocator());
258     uint32_t buf;
259 
260     bv.SetBit(0);
261     bv.SetBit(17);
262     bv.SetBit(26);
263     EXPECT_EQ(sizeof(buf), bv.GetSizeOf());
264 
265     bv.CopyTo(&buf, sizeof(buf));
266     EXPECT_EQ(0x04020001u, buf);
267   }
268 
269   {
270     // Test copying when the `bv.storage_` is longer than `buf`. As long as
271     // `buf` is long enough to hold all set bits, copying should succeed.
272     BitVector bv(0, true, Allocator::GetCallocAllocator());
273     uint8_t buf[5];
274 
275     bv.SetBit(18);
276     bv.SetBit(39);
277     EXPECT_LT(sizeof(buf), bv.GetSizeOf());
278 
279     bv.CopyTo(buf, sizeof(buf));
280     EXPECT_EQ(0x00u, buf[0]);
281     EXPECT_EQ(0x00u, buf[1]);
282     EXPECT_EQ(0x04u, buf[2]);
283     EXPECT_EQ(0x00u, buf[3]);
284     EXPECT_EQ(0x80u, buf[4]);
285   }
286 
287   {
288     // Test zero padding when `bv.storage_` is shorter than `buf`.
289     BitVector bv(0, true, Allocator::GetCallocAllocator());
290     uint32_t buf[2];
291 
292     bv.SetBit(18);
293     bv.SetBit(31);
294     EXPECT_GT(sizeof(buf), bv.GetSizeOf());
295 
296     bv.CopyTo(buf, sizeof(buf));
297     EXPECT_EQ(0x80040000U, buf[0]);
298     EXPECT_EQ(0x00000000U, buf[1]);
299   }
300 }
301 
TEST(BitVector,TransformIterator)302 TEST(BitVector, TransformIterator) {
303   BitVector bv(16, false, Allocator::GetCallocAllocator());
304   bv.SetBit(4);
305   bv.SetBit(8);
306 
307   auto indexs = bv.Indexes();
308   for (int32_t negative :
309        MakeTransformRange(indexs, [](uint32_t idx) { return -1 * static_cast<int32_t>(idx); })) {
310     EXPECT_TRUE(negative == -4 || negative == -8);
311   }
312 }
313 
314 class SingleAllocator : public Allocator {
315  public:
SingleAllocator()316   SingleAllocator() : alloc_count_(0), free_count_(0) {}
~SingleAllocator()317   ~SingleAllocator() {
318     EXPECT_EQ(alloc_count_, 1u);
319     EXPECT_EQ(free_count_, 1u);
320   }
321 
Alloc(size_t s)322   void* Alloc(size_t s) override {
323     EXPECT_LT(s, 1024ull);
324     EXPECT_EQ(alloc_count_, free_count_);
325     ++alloc_count_;
326     return bytes_.begin();
327   }
328 
Free(void *)329   void Free(void*) override {
330     ++free_count_;
331   }
332 
AllocCount() const333   uint32_t AllocCount() const {
334     return alloc_count_;
335   }
FreeCount() const336   uint32_t FreeCount() const {
337     return free_count_;
338   }
339 
340  private:
341   std::array<uint8_t, 1024> bytes_;
342   uint32_t alloc_count_;
343   uint32_t free_count_;
344 };
345 
TEST(BitVector,MovementFree)346 TEST(BitVector, MovementFree) {
347   SingleAllocator alloc;
348   {
349     BitVector bv(16, false, &alloc);
350     bv.SetBit(13);
351     EXPECT_EQ(alloc.FreeCount(), 0u);
352     EXPECT_EQ(alloc.AllocCount(), 1u);
353     ASSERT_TRUE(bv.GetRawStorage() != nullptr);
354     EXPECT_TRUE(bv.IsBitSet(13));
355     {
356       BitVector bv2(std::move(bv));
357       // NOLINTNEXTLINE - checking underlying storage has been freed
358       ASSERT_TRUE(bv.GetRawStorage() == nullptr);
359       EXPECT_TRUE(bv2.IsBitSet(13));
360       EXPECT_EQ(alloc.FreeCount(), 0u);
361       EXPECT_EQ(alloc.AllocCount(), 1u);
362     }
363     EXPECT_EQ(alloc.FreeCount(), 1u);
364     EXPECT_EQ(alloc.AllocCount(), 1u);
365   }
366   EXPECT_EQ(alloc.FreeCount(), 1u);
367   EXPECT_EQ(alloc.AllocCount(), 1u);
368 }
369 
370 }  // namespace art
371