jdk

1
/*
2
 * Copyright (c) 2016, 2022, Oracle and/or its affiliates. All rights reserved.
3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4
 *
5
 * This code is free software; you can redistribute it and/or modify it
6
 * under the terms of the GNU General Public License version 2 only, as
7
 * published by the Free Software Foundation.
8
 *
9
 * This code is distributed in the hope that it will be useful, but WITHOUT
10
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12
 * version 2 for more details (a copy is included in the LICENSE file that
13
 * accompanied this code).
14
 *
15
 * You should have received a copy of the GNU General Public License version
16
 * 2 along with this work; if not, write to the Free Software Foundation,
17
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18
 *
19
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20
 * or visit www.oracle.com if you need additional information or have any
21
 * questions.
22
 */
23

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"
30

31
class BitMapTest {
32

33
  template <class ResizableBitMapClass>
34
  static void fillBitMap(ResizableBitMapClass& map) {
35
    map.set_bit(1);
36
    map.set_bit(3);
37
    map.set_bit(17);
38
    map.set_bit(512);
39
  }
40

41
  template <class ResizableBitMapClass>
42
  static void testResize(BitMap::idx_t start_size) {
43
    ResourceMark rm;
44

45
    ResizableBitMapClass map(start_size);
46
    map.resize(BITMAP_SIZE);
47
    fillBitMap(map);
48

49
    ResizableBitMapClass map2(BITMAP_SIZE);
50
    fillBitMap(map2);
51
    EXPECT_TRUE(map.is_same(map2)) << "With start_size " << start_size;
52
  }
53

54
 public:
55
  const static BitMap::idx_t BITMAP_SIZE = 1024;
56

57

58
  template <class ResizableBitMapClass>
59
  static void testResizeGrow() {
60
    testResize<ResizableBitMapClass>(0);
61
    testResize<ResizableBitMapClass>(BITMAP_SIZE >> 3);
62
  }
63

64
  template <class ResizableBitMapClass>
65
  static void testResizeSame() {
66
    testResize<ResizableBitMapClass>(BITMAP_SIZE);
67
  }
68

69
  template <class ResizableBitMapClass>
70
  static void testResizeShrink() {
71
    testResize<ResizableBitMapClass>(BITMAP_SIZE * 2);
72
  }
73

74
  template <class InitializableBitMapClass>
75
  static void testInitialize() {
76
    ResourceMark rm;
77

78
    InitializableBitMapClass map;
79
    map.initialize(BITMAP_SIZE);
80
    fillBitMap(map);
81

82
    InitializableBitMapClass map2(BITMAP_SIZE);
83
    fillBitMap(map2);
84
    EXPECT_TRUE(map.is_same(map2));
85
  }
86

87
  template <class ReinitializableBitMapClass>
88
  static void testReinitialize(BitMap::idx_t init_size) {
89
    ResourceMark rm;
90

91
    ReinitializableBitMapClass  map(init_size);
92
    map.reinitialize(BITMAP_SIZE);
93
    fillBitMap(map);
94

95
    ReinitializableBitMapClass map2(BITMAP_SIZE);
96
    fillBitMap(map2);
97
    EXPECT_TRUE(map.is_same(map2)) << "With init_size " << init_size;
98
  }
99

100
#ifdef ASSERT
101
  template <class PrintableBitMapClass>
102
  static void testPrintOn(BitMap::idx_t size) {
103
    ResourceMark rm;
104

105
    PrintableBitMapClass map(size);
106
    if (size > 0) {
107
      map.set_bit(size / 2);
108
    }
109

110
    LogStreamHandle(Info, test) stream;
111
    map.print_on(&stream);
112
  }
113

114
#endif
115
};
116

117
class BitMapTruncateTest {
118

119
 public:
120
  const static BitMap::idx_t BITMAP_SIZE = 128;
121

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) {
126
        if (bit < size) {
127
            map.set_bit(bit);
128
        }
129
    }
130
  }
131

132
  template <class ResizableBitMapClass>
133
  static void testTruncateOneWord() {
134
    ResourceMark rm;
135

136
    ResizableBitMapClass map(64);
137
    map.set_bit(0);
138
    map.set_bit(1);
139
    map.set_bit(2);
140
    map.set_bit(3);
141

142
    ResizableBitMapClass result(2);
143
    result.set_bit(0);
144
    result.set_bit(1);
145

146
    map.truncate(1, 3);
147

148
    EXPECT_TRUE(map.is_same(result));
149
  }
150

151
  template <class ResizableBitMapClass>
152
  static void testTruncateSame() {
153
    // Resulting map should be the same as the original
154
    ResourceMark rm;
155
    ResizableBitMapClass expected(BITMAP_SIZE);
156
    fillBitMap(expected, BITMAP_SIZE);
157

158
    ResizableBitMapClass map(BITMAP_SIZE);
159
    fillBitMap(map, BITMAP_SIZE);
160
    map.truncate(0, BITMAP_SIZE);
161

162
    EXPECT_TRUE(map.is_same(expected));
163
  }
164

165
  template <class ResizableBitMapClass>
166
  static void testTruncateStart() {
167
    // Resulting map should start at the beginning of the original
168
    ResourceMark rm;
169
    ResizableBitMapClass expected(64);
170
    fillBitMap(expected, 64);
171

172
    ResizableBitMapClass map(BITMAP_SIZE);
173
    fillBitMap(map, BITMAP_SIZE);
174
    map.truncate(0, 64);
175

176
    EXPECT_TRUE(map.is_same(expected));
177
  }
178

179
  template <class ResizableBitMapClass>
180
  static void testTruncateEnd() {
181
    // Resulting map should end at the end of the original
182
    ResourceMark rm;
183
    ResizableBitMapClass expected(64);
184
    expected.set_bit(0);
185
    expected.set_bit(31);
186
    expected.set_bit(63);
187

188
    ResizableBitMapClass map(BITMAP_SIZE);
189
    fillBitMap(map, BITMAP_SIZE);
190
    map.truncate(64, 128);
191

192
    EXPECT_TRUE(map.is_same(expected));
193
  }
194

195
  template <class ResizableBitMapClass>
196
  static void testTruncateMiddle() {
197
    // Resulting map should end at the end of the original
198
    ResourceMark rm;
199
    ResizableBitMapClass expected(64);
200
    expected.set_bit(31);
201
    expected.set_bit(32);
202
    expected.set_bit(63);
203

204
    ResizableBitMapClass map(BITMAP_SIZE);
205
    fillBitMap(map, BITMAP_SIZE);
206
    map.truncate(32, 96);
207

208
    EXPECT_TRUE(map.is_same(expected));
209
  }
210

211
  template <class ResizableBitMapClass>
212
  static void testTruncateStartUnaligned() {
213
    // Resulting map should start at the beginning of the original
214
    ResourceMark rm;
215
    ResizableBitMapClass expected(96);
216
    fillBitMap(expected, 96);
217

218
    ResizableBitMapClass map(BITMAP_SIZE);
219
    fillBitMap(map, BITMAP_SIZE);
220
    map.truncate(0, 96);
221

222
    EXPECT_TRUE(map.is_same(expected));
223
  }
224

225
  template <class ResizableBitMapClass>
226
  static void testTruncateEndUnaligned() {
227
    // Resulting map should end at the end of the original
228
    ResourceMark rm;
229
    ResizableBitMapClass expected(97);
230
    expected.set_bit(0);
231
    expected.set_bit(32);
232
    expected.set_bit(33);
233
    expected.set_bit(64);
234
    expected.set_bit(96);
235

236
    ResizableBitMapClass map(BITMAP_SIZE);
237
    fillBitMap(map, BITMAP_SIZE);
238
    map.truncate(31, 128);
239

240
    EXPECT_TRUE(map.is_same(expected));
241
  }
242

243
  template <class ResizableBitMapClass>
244
  static void testRandom() {
245
    for (int i = 0; i < 100; i++) {
246
      ResourceMark rm;
247

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);
252

253
      ResizableBitMapClass map(size);
254
      ResizableBitMapClass result(truncate_size);
255

256
      for (BitMap::idx_t idx = 0; idx < truncate_start; idx++) {
257
        if (os::random() % 2 == 0) {
258
          map.set_bit(idx);
259
        }
260
      }
261

262
      for (BitMap::idx_t idx = 0; idx < truncate_size; idx++) {
263
        if (os::random() % 2 == 0) {
264
          map.set_bit(truncate_start + idx);
265
          result.set_bit(idx);
266
        }
267
      }
268

269
      map.truncate(truncate_start, truncate_start + truncate_size);
270

271
      EXPECT_TRUE(map.is_same(result));
272
    }
273
  }
274
};
275

276
// TestArenaBitMap is the shorthand combination of Arena and ArenaBitMap.
277
// Multiple inheritance guarantees to construct Arena first.
278
class TestArenaBitMap : private Arena, public ArenaBitMap {
279
 public:
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) {}
283
};
284

285
class TestCHeapBitMap : public CHeapBitMap {
286
public:
287
  TestCHeapBitMap(size_t size = 0) : CHeapBitMap(size, mtTest) {}
288

289
};
290

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";
298
}
299

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";
307
}
308

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";
316
}
317

318
// Verify that when growing with clear, all added bits get cleared,
319
// even those corresponding to a partial word after the old size.
320
TEST_VM(BitMap, resize_grow_clear) {
321
  ResourceMark rm;
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 /* clear */);
325
  bm.set_bit(size - 1);
326
  EXPECT_EQ(bm.count_one_bits(), size_t(1));
327
  // Discard the only set bit.  But it might still be "set" in the
328
  // partial word beyond the new size.
329
  bm.resize(size - word_size/2);
330
  EXPECT_EQ(bm.count_one_bits(), size_t(0));
331
  // Grow to include the previously set bit.  Verify that it ended up cleared.
332
  bm.resize(2 * size);
333
  EXPECT_EQ(bm.count_one_bits(), size_t(0));
334
}
335

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";
343
}
344

345
TEST_VM(BitMap, reinitialize) {
346
  constexpr BitMap::idx_t sizes[] = {0, BitMapTest::BITMAP_SIZE >> 3, BitMapTest::BITMAP_SIZE};
347

348
  for (auto size : sizes) {
349
    BitMapTest::testReinitialize<ResourceBitMap>(size);
350
    BitMapTest::testReinitialize<TestArenaBitMap>(size);
351
  }
352
}
353

354
#ifdef ASSERT
355

356
TEST_VM(BitMap, print_on) {
357
  constexpr BitMap::idx_t sizes[] = {0, BitMapTest::BITMAP_SIZE >> 3, BitMapTest::BITMAP_SIZE};
358

359
  for (auto size : sizes) {
360
    BitMapTest::testPrintOn<ResourceBitMap>(size);
361
    BitMapTest::testPrintOn<TestArenaBitMap>(size);
362
  }
363
}
364

365
#endif
366

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";
374
}
375

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";
383
}
384

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";
392
}
393

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";
401
}
402

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";
410
}
411

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";
419
}
420

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";
428
}
429

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";
437
}
438