24
#include "precompiled.hpp"
25
#include "logging/logStream.hpp"
26
#include "memory/arena.hpp"
27
#include "memory/resourceArea.hpp"
28
#include "utilities/bitMap.inline.hpp"
29
#include "unittest.hpp"
33
template <class ResizableBitMapClass>
34
static void fillBitMap(ResizableBitMapClass& map) {
41
template <class ResizableBitMapClass>
42
static void testResize(BitMap::idx_t start_size) {
45
ResizableBitMapClass map(start_size);
46
map.resize(BITMAP_SIZE);
49
ResizableBitMapClass map2(BITMAP_SIZE);
51
EXPECT_TRUE(map.is_same(map2)) << "With start_size " << start_size;
55
const static BitMap::idx_t BITMAP_SIZE = 1024;
58
template <class ResizableBitMapClass>
59
static void testResizeGrow() {
60
testResize<ResizableBitMapClass>(0);
61
testResize<ResizableBitMapClass>(BITMAP_SIZE >> 3);
64
template <class ResizableBitMapClass>
65
static void testResizeSame() {
66
testResize<ResizableBitMapClass>(BITMAP_SIZE);
69
template <class ResizableBitMapClass>
70
static void testResizeShrink() {
71
testResize<ResizableBitMapClass>(BITMAP_SIZE * 2);
74
template <class InitializableBitMapClass>
75
static void testInitialize() {
78
InitializableBitMapClass map;
79
map.initialize(BITMAP_SIZE);
82
InitializableBitMapClass map2(BITMAP_SIZE);
84
EXPECT_TRUE(map.is_same(map2));
87
template <class ReinitializableBitMapClass>
88
static void testReinitialize(BitMap::idx_t init_size) {
91
ReinitializableBitMapClass map(init_size);
92
map.reinitialize(BITMAP_SIZE);
95
ReinitializableBitMapClass map2(BITMAP_SIZE);
97
EXPECT_TRUE(map.is_same(map2)) << "With init_size " << init_size;
101
template <class PrintableBitMapClass>
102
static void testPrintOn(BitMap::idx_t size) {
105
PrintableBitMapClass map(size);
107
map.set_bit(size / 2);
110
LogStreamHandle(Info, test) stream;
111
map.print_on(&stream);
117
class BitMapTruncateTest {
120
const static BitMap::idx_t BITMAP_SIZE = 128;
122
template <class ResizableBitMapClass>
123
static void fillBitMap(ResizableBitMapClass& map, BitMap::idx_t size) {
124
BitMap::idx_t set_bits[] = {0, 31, 63, 64, 95, 127};
125
for (BitMap::idx_t bit : set_bits) {
132
template <class ResizableBitMapClass>
133
static void testTruncateOneWord() {
136
ResizableBitMapClass map(64);
142
ResizableBitMapClass result(2);
148
EXPECT_TRUE(map.is_same(result));
151
template <class ResizableBitMapClass>
152
static void testTruncateSame() {
155
ResizableBitMapClass expected(BITMAP_SIZE);
156
fillBitMap(expected, BITMAP_SIZE);
158
ResizableBitMapClass map(BITMAP_SIZE);
159
fillBitMap(map, BITMAP_SIZE);
160
map.truncate(0, BITMAP_SIZE);
162
EXPECT_TRUE(map.is_same(expected));
165
template <class ResizableBitMapClass>
166
static void testTruncateStart() {
169
ResizableBitMapClass expected(64);
170
fillBitMap(expected, 64);
172
ResizableBitMapClass map(BITMAP_SIZE);
173
fillBitMap(map, BITMAP_SIZE);
176
EXPECT_TRUE(map.is_same(expected));
179
template <class ResizableBitMapClass>
180
static void testTruncateEnd() {
183
ResizableBitMapClass expected(64);
185
expected.set_bit(31);
186
expected.set_bit(63);
188
ResizableBitMapClass map(BITMAP_SIZE);
189
fillBitMap(map, BITMAP_SIZE);
190
map.truncate(64, 128);
192
EXPECT_TRUE(map.is_same(expected));
195
template <class ResizableBitMapClass>
196
static void testTruncateMiddle() {
199
ResizableBitMapClass expected(64);
200
expected.set_bit(31);
201
expected.set_bit(32);
202
expected.set_bit(63);
204
ResizableBitMapClass map(BITMAP_SIZE);
205
fillBitMap(map, BITMAP_SIZE);
206
map.truncate(32, 96);
208
EXPECT_TRUE(map.is_same(expected));
211
template <class ResizableBitMapClass>
212
static void testTruncateStartUnaligned() {
215
ResizableBitMapClass expected(96);
216
fillBitMap(expected, 96);
218
ResizableBitMapClass map(BITMAP_SIZE);
219
fillBitMap(map, BITMAP_SIZE);
222
EXPECT_TRUE(map.is_same(expected));
225
template <class ResizableBitMapClass>
226
static void testTruncateEndUnaligned() {
229
ResizableBitMapClass expected(97);
231
expected.set_bit(32);
232
expected.set_bit(33);
233
expected.set_bit(64);
234
expected.set_bit(96);
236
ResizableBitMapClass map(BITMAP_SIZE);
237
fillBitMap(map, BITMAP_SIZE);
238
map.truncate(31, 128);
240
EXPECT_TRUE(map.is_same(expected));
243
template <class ResizableBitMapClass>
244
static void testRandom() {
245
for (int i = 0; i < 100; i++) {
248
const size_t max_size = 1024;
249
const size_t size = os::random() % max_size + 1;
250
const size_t truncate_size = os::random() % size + 1;
251
const size_t truncate_start = size == truncate_size ? 0 : os::random() % (size - truncate_size);
253
ResizableBitMapClass map(size);
254
ResizableBitMapClass result(truncate_size);
256
for (BitMap::idx_t idx = 0; idx < truncate_start; idx++) {
257
if (os::random() % 2 == 0) {
262
for (BitMap::idx_t idx = 0; idx < truncate_size; idx++) {
263
if (os::random() % 2 == 0) {
264
map.set_bit(truncate_start + idx);
269
map.truncate(truncate_start, truncate_start + truncate_size);
271
EXPECT_TRUE(map.is_same(result));
278
class TestArenaBitMap : private Arena, public ArenaBitMap {
280
TestArenaBitMap() : TestArenaBitMap(0) {}
281
TestArenaBitMap(idx_t size_in_bits, bool clear = true) : Arena(mtTest),
282
ArenaBitMap(static_cast<Arena*>(this), size_in_bits, clear) {}
285
class TestCHeapBitMap : public CHeapBitMap {
287
TestCHeapBitMap(size_t size = 0) : CHeapBitMap(size, mtTest) {}
291
TEST_VM(BitMap, resize_grow) {
292
BitMapTest::testResizeGrow<ResourceBitMap>();
293
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
294
BitMapTest::testResizeGrow<TestCHeapBitMap>();
295
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
296
BitMapTest::testResizeGrow<TestArenaBitMap>();
297
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
300
TEST_VM(BitMap, resize_shrink) {
301
BitMapTest::testResizeShrink<ResourceBitMap>();
302
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
303
BitMapTest::testResizeShrink<TestCHeapBitMap>();
304
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
305
BitMapTest::testResizeShrink<TestArenaBitMap>();
306
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
309
TEST_VM(BitMap, resize_same) {
310
BitMapTest::testResizeSame<ResourceBitMap>();
311
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
312
BitMapTest::testResizeSame<TestCHeapBitMap>();
313
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
314
BitMapTest::testResizeSame<TestArenaBitMap>();
315
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
320
TEST_VM(BitMap, resize_grow_clear) {
322
const size_t word_size = sizeof(BitMap::bm_word_t) * BitsPerByte;
323
const size_t size = 4 * word_size;
324
ResourceBitMap bm(size, true );
325
bm.set_bit(size - 1);
326
EXPECT_EQ(bm.count_one_bits(), size_t(1));
329
bm.resize(size - word_size/2);
330
EXPECT_EQ(bm.count_one_bits(), size_t(0));
333
EXPECT_EQ(bm.count_one_bits(), size_t(0));
336
TEST_VM(BitMap, initialize) {
337
BitMapTest::testInitialize<ResourceBitMap>();
338
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
339
BitMapTest::testInitialize<TestCHeapBitMap>();
340
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
341
BitMapTest::testInitialize<TestArenaBitMap>();
342
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
345
TEST_VM(BitMap, reinitialize) {
346
constexpr BitMap::idx_t sizes[] = {0, BitMapTest::BITMAP_SIZE >> 3, BitMapTest::BITMAP_SIZE};
348
for (auto size : sizes) {
349
BitMapTest::testReinitialize<ResourceBitMap>(size);
350
BitMapTest::testReinitialize<TestArenaBitMap>(size);
356
TEST_VM(BitMap, print_on) {
357
constexpr BitMap::idx_t sizes[] = {0, BitMapTest::BITMAP_SIZE >> 3, BitMapTest::BITMAP_SIZE};
359
for (auto size : sizes) {
360
BitMapTest::testPrintOn<ResourceBitMap>(size);
361
BitMapTest::testPrintOn<TestArenaBitMap>(size);
367
TEST_VM(BitMap, truncate_same) {
368
BitMapTruncateTest::testTruncateSame<ResourceBitMap>();
369
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
370
BitMapTruncateTest::testTruncateSame<TestCHeapBitMap>();
371
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
372
BitMapTruncateTest::testTruncateSame<TestArenaBitMap>();
373
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
376
TEST_VM(BitMap, truncate_start) {
377
BitMapTruncateTest::testTruncateStart<ResourceBitMap>();
378
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
379
BitMapTruncateTest::testTruncateStart<TestCHeapBitMap>();
380
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
381
BitMapTruncateTest::testTruncateStart<TestArenaBitMap>();
382
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
385
TEST_VM(BitMap, truncate_end) {
386
BitMapTruncateTest::testTruncateEnd<ResourceBitMap>();
387
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
388
BitMapTruncateTest::testTruncateEnd<TestCHeapBitMap>();
389
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
390
BitMapTruncateTest::testTruncateEnd<TestArenaBitMap>();
391
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
394
TEST_VM(BitMap, truncate_middle) {
395
BitMapTruncateTest::testTruncateMiddle<ResourceBitMap>();
396
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
397
BitMapTruncateTest::testTruncateMiddle<TestCHeapBitMap>();
398
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
399
BitMapTruncateTest::testTruncateMiddle<TestArenaBitMap>();
400
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
403
TEST_VM(BitMap, truncate_start_unaligned) {
404
BitMapTruncateTest::testTruncateStartUnaligned<ResourceBitMap>();
405
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
406
BitMapTruncateTest::testTruncateStartUnaligned<TestCHeapBitMap>();
407
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
408
BitMapTruncateTest::testTruncateStartUnaligned<TestArenaBitMap>();
409
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
412
TEST_VM(BitMap, truncate_end_unaligned) {
413
BitMapTruncateTest::testTruncateEndUnaligned<ResourceBitMap>();
414
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
415
BitMapTruncateTest::testTruncateEndUnaligned<TestCHeapBitMap>();
416
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
417
BitMapTruncateTest::testTruncateEndUnaligned<TestArenaBitMap>();
418
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
421
TEST_VM(BitMap, truncate_one_word) {
422
BitMapTruncateTest::testTruncateOneWord<ResourceBitMap>();
423
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
424
BitMapTruncateTest::testTruncateOneWord<TestCHeapBitMap>();
425
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
426
BitMapTruncateTest::testTruncateOneWord<TestArenaBitMap>();
427
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";
430
TEST_VM(BitMap, truncate_random) {
431
BitMapTruncateTest::testRandom<ResourceBitMap>();
432
EXPECT_FALSE(HasFailure()) << "Failed on type ResourceBitMap";
433
BitMapTruncateTest::testRandom<TestCHeapBitMap>();
434
EXPECT_FALSE(HasFailure()) << "Failed on type CHeapBitMap";
435
BitMapTruncateTest::testRandom<TestArenaBitMap>();
436
EXPECT_FALSE(HasFailure()) << "Failed on type ArenaBitMap";