1 /*
2 * Copyright (c) 2016, 2019, 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 "utilities/align.hpp"
26 #include "utilities/bitMap.inline.hpp"
27 #include "utilities/copy.hpp"
28 #include "utilities/debug.hpp"
29 #include "utilities/globalDefinitions.hpp"
30 #include <stdlib.h>
31 #include "unittest.hpp"
32
33 typedef BitMap::idx_t idx_t;
34 typedef BitMap::bm_word_t bm_word_t;
35
word_align_down(idx_t bit)36 inline idx_t word_align_down(idx_t bit) {
37 return align_down(bit, BitsPerWord);
38 }
39
40 class BitMapMemory {
41 private:
42 idx_t _words;
43 bm_word_t* _memory;
44
45 public:
BitMapMemory(idx_t bits)46 BitMapMemory(idx_t bits) :
47 _words(BitMap::calc_size_in_words(bits)),
48 _memory(static_cast<bm_word_t*>(malloc(_words * sizeof(bm_word_t))))
49 { }
50
~BitMapMemory()51 ~BitMapMemory() {
52 free(_memory);
53 }
54
make_view(idx_t bits,bm_word_t value)55 BitMapView make_view(idx_t bits, bm_word_t value) {
56 vmassert(BitMap::calc_size_in_words(bits) <= _words, "invalid request");
57 STATIC_ASSERT(sizeof(bm_word_t) == sizeof(HeapWord));
58 Copy::fill_to_aligned_words((HeapWord*)_memory, _words, value);
59 return BitMapView(_memory, bits);
60 }
61
memory()62 bm_word_t* memory() { return _memory; }
63 };
64
65 const idx_t aligned_size = 4 * BitsPerWord;
66 const idx_t unaligned_size = aligned_size - (BitsPerWord / 2);
67
make_even_bits()68 static bm_word_t make_even_bits() {
69 bm_word_t result = 1;
70 while (true) {
71 bm_word_t next = (result << 2) | 1;
72 if (next == result) {
73 return result;
74 }
75 result = next;
76 }
77 }
78
79 const bm_word_t even_bits = make_even_bits();
80 const bm_word_t odd_bits = ~even_bits;
81 const bm_word_t one_bits = ~bm_word_t(0);
82 const bm_word_t zero_bits = 0;
83
84 // Scoped set a clear bit and restore to clear.
85 class WithBitSet {
86 private:
87 BitMap& _bm;
88 idx_t _index;
89
90 public:
WithBitSet(BitMap & bm,idx_t index)91 WithBitSet(BitMap& bm, idx_t index) : _bm(bm), _index(index) {
92 // Failure may indicate test bug; can't use ASSERT_xxx in constructor.
93 EXPECT_FALSE(_bm.at(_index));
94 bm.set_bit(_index);
95 }
96
~WithBitSet()97 ~WithBitSet() {
98 _bm.clear_bit(_index);
99 }
100 };
101
102 // Scoped clear a set bit and restore to set.
103 class WithBitClear {
104 private:
105 BitMap& _bm;
106 idx_t _index;
107
108 public:
WithBitClear(BitMap & bm,idx_t index)109 WithBitClear(BitMap& bm, idx_t index) : _bm(bm), _index(index) {
110 // Failure may indicate test bug; can't use ASSERT_xxx in constructor.
111 EXPECT_TRUE(_bm.at(_index));
112 bm.clear_bit(_index);
113 }
114
~WithBitClear()115 ~WithBitClear() {
116 _bm.set_bit(_index);
117 }
118 };
119
120 //////////////////////////////////////////////////////////////////////////////
121 // bool is_same(const BitMap& bits);
122
TEST(BitMap,is_same__aligned)123 TEST(BitMap, is_same__aligned) {
124 BitMapMemory mx(aligned_size);
125 BitMapMemory my(aligned_size);
126
127 BitMapView x = mx.make_view(aligned_size, even_bits);
128 BitMapView y = my.make_view(aligned_size, even_bits);
129 EXPECT_TRUE(x.is_same(y));
130
131 WithBitClear wbc(x, aligned_size / 2);
132 EXPECT_FALSE(x.is_same(y));
133 }
134
TEST(BitMap,is_same__unaligned)135 TEST(BitMap, is_same__unaligned) {
136 BitMapMemory mx(aligned_size);
137 BitMapMemory my(aligned_size);
138
139 BitMapView x = mx.make_view(unaligned_size, even_bits);
140 BitMapView y = my.make_view(unaligned_size, even_bits);
141
142 // Check that a difference beyond the end of x/y doesn't count.
143 {
144 BitMapView aligned = BitMapView(mx.memory(), aligned_size);
145 const idx_t index = aligned_size - 2;
146 STATIC_ASSERT(unaligned_size <= index);
147
148 WithBitClear wbc(aligned, index);
149 EXPECT_TRUE(x.is_same(y));
150 }
151
152 // Check that a difference in the final partial word does count.
153 {
154 idx_t index = unaligned_size - 2;
155 ASSERT_LE(word_align_down(unaligned_size), index);
156
157 WithBitClear wbc(y, index);
158 EXPECT_FALSE(x.is_same(y));
159 }
160 }
161
162 //////////////////////////////////////////////////////////////////////////////
163 // bool is_full();
164 // bool is_empty();
165
TEST(BitMap,is_full_or_empty__aligned)166 TEST(BitMap, is_full_or_empty__aligned) {
167 BitMapMemory mx(aligned_size);
168
169 {
170 BitMapView x = mx.make_view(aligned_size, even_bits);
171 EXPECT_FALSE(x.is_full());
172 EXPECT_FALSE(x.is_empty());
173 }
174
175 {
176 BitMapView x = mx.make_view(aligned_size, zero_bits);
177 EXPECT_FALSE(x.is_full());
178 EXPECT_TRUE(x.is_empty());
179 }
180
181 {
182 BitMapView x = mx.make_view(aligned_size, one_bits);
183 EXPECT_TRUE(x.is_full());
184 EXPECT_FALSE(x.is_empty());
185 }
186 }
187
TEST(BitMap,is_full__unaligned)188 TEST(BitMap, is_full__unaligned) {
189 BitMapMemory mx(aligned_size);
190
191 BitMapView x = mx.make_view(unaligned_size, one_bits);
192 EXPECT_TRUE(x.is_full());
193
194 // Check that a missing bit beyond the end doesn't count.
195 {
196 idx_t index = aligned_size - 1;
197 BitMapView aligned = BitMapView(mx.memory(), aligned_size);
198
199 WithBitClear wcb(aligned, index);
200 EXPECT_FALSE(aligned.is_full());
201 EXPECT_TRUE(x.is_full());
202 }
203
204 // Check that a missing bit in the final partial word does count.
205 {
206 WithBitClear wcb(x, unaligned_size - 1);
207 EXPECT_FALSE(x.is_full());
208 }
209 }
210
TEST(BitMap,is_empty__unaligned)211 TEST(BitMap, is_empty__unaligned) {
212 BitMapMemory mx(aligned_size);
213
214 BitMapView x = mx.make_view(unaligned_size, zero_bits);
215 EXPECT_TRUE(x.is_empty());
216
217 // Check that a set bit beyond the end doesn't count.
218 {
219 idx_t index = aligned_size - 1;
220 BitMapView aligned = BitMapView(mx.memory(), aligned_size);
221
222 WithBitSet wbs(aligned, index);
223 EXPECT_FALSE(aligned.is_empty());
224 EXPECT_TRUE(x.is_empty());
225 }
226
227 // Check that a set bit in the final partial word does count.
228 {
229 WithBitSet wbs(x, unaligned_size - 1);
230 EXPECT_FALSE(x.is_empty());
231 }
232 }
233
234 //////////////////////////////////////////////////////////////////////////////
235 // bool contains(const BitMap& bits);
236
TEST(BitMap,contains__aligned)237 TEST(BitMap, contains__aligned) {
238 BitMapMemory mx(aligned_size);
239 BitMapMemory my(aligned_size);
240
241 BitMapView x = mx.make_view(aligned_size, even_bits);
242 BitMapView y = my.make_view(aligned_size, even_bits);
243 EXPECT_TRUE(x.contains(y));
244
245 WithBitClear wbc(x, aligned_size / 2);
246 EXPECT_FALSE(x.contains(y));
247 }
248
TEST(BitMap,contains__unaligned)249 TEST(BitMap, contains__unaligned) {
250 BitMapMemory mx(aligned_size);
251 BitMapMemory my(aligned_size);
252
253 BitMapView x = mx.make_view(unaligned_size, even_bits);
254 BitMapView y = my.make_view(unaligned_size, even_bits);
255
256 // Check that a missing bit beyond the end of x doesn't count.
257 {
258 BitMapView aligned = BitMapView(mx.memory(), aligned_size);
259 const idx_t index = aligned_size - 2;
260 STATIC_ASSERT(unaligned_size <= index);
261
262 WithBitClear wbc(aligned, index);
263 EXPECT_TRUE(x.contains(y));
264 }
265
266 // Check that a missing bit in the final partial word does count.
267 {
268 idx_t index = unaligned_size - 2;
269 ASSERT_LE(word_align_down(unaligned_size), index);
270
271 WithBitClear wbc(x, index);
272 EXPECT_FALSE(x.contains(y));
273 }
274 }
275
276 //////////////////////////////////////////////////////////////////////////////
277 // bool intersects(const BitMap& bits);
278
TEST(BitMap,intersects__aligned)279 TEST(BitMap, intersects__aligned) {
280 BitMapMemory mx(aligned_size);
281 BitMapMemory my(aligned_size);
282
283 BitMapView x = mx.make_view(aligned_size, even_bits);
284 BitMapView y = my.make_view(aligned_size, zero_bits);
285 EXPECT_FALSE(x.intersects(y));
286
287 ASSERT_TRUE(x.at(aligned_size / 2));
288 WithBitSet wbs(y, aligned_size / 2);
289 EXPECT_TRUE(x.intersects(y));
290 }
291
TEST(BitMap,intersects__unaligned)292 TEST(BitMap, intersects__unaligned) {
293 BitMapMemory mx(aligned_size);
294 BitMapMemory my(aligned_size);
295
296 BitMapView x = mx.make_view(unaligned_size, even_bits);
297 BitMapView y = my.make_view(unaligned_size, zero_bits);
298 EXPECT_FALSE(x.intersects(y));
299
300 // Check that adding a bit beyond the end of y doesn't count.
301 {
302 BitMapView aligned_x = BitMapView(mx.memory(), aligned_size);
303 BitMapView aligned_y = BitMapView(my.memory(), aligned_size);
304 const idx_t index = aligned_size - 2;
305 STATIC_ASSERT(unaligned_size <= index);
306 ASSERT_TRUE(aligned_x.at(index));
307
308 WithBitSet wbs(aligned_y, index);
309 EXPECT_FALSE(x.intersects(y));
310 }
311
312 // Check that adding a bit in the final partial word does count.
313 {
314 idx_t index = unaligned_size - 2;
315 ASSERT_LE(word_align_down(unaligned_size), index);
316 ASSERT_TRUE(x.at(index));
317
318 WithBitSet wbs(y, index);
319 EXPECT_TRUE(x.intersects(y));
320 }
321 }
322
323 //////////////////////////////////////////////////////////////////////////////
324 // void set_from(const BitMap& bits);
325 // void set_union(const BitMap& bits);
326 // void set_difference(const BitMap& bits);
327 // void set_intersection(const BitMap& bits);
328 //
329 // bool set_union_with_result(const BitMap& bits);
330 // bool set_difference_with_result(const BitMap& bits);
331 // bool set_intersection_with_result(const BitMap& bits);
332
check_tail_unmodified(BitMapMemory & mem,idx_t bits,bm_word_t fill_word)333 static void check_tail_unmodified(BitMapMemory& mem,
334 idx_t bits,
335 bm_word_t fill_word) {
336 if (!is_aligned(bits, BitsPerWord)) {
337 idx_t last_word_bit_index = word_align_down(bits);
338 idx_t last_word_index = BitMap::calc_size_in_words(last_word_bit_index);
339 bm_word_t last_word = mem.memory()[last_word_index];
340 idx_t shift = bits - last_word_bit_index;
341 EXPECT_EQ(fill_word >> shift, last_word >> shift);
342 }
343 }
344
check_mod_setop(void (BitMap::* f)(const BitMap &),idx_t bits,bm_word_t wx,bm_word_t wy,bm_word_t wexp)345 static void check_mod_setop(void (BitMap::*f)(const BitMap&),
346 idx_t bits,
347 bm_word_t wx,
348 bm_word_t wy,
349 bm_word_t wexp) {
350 BitMapMemory mx(bits);
351 BitMapMemory my(bits);
352 BitMapMemory mexp(bits);
353
354 BitMapView x = mx.make_view(bits, wx);
355 BitMapView y = my.make_view(bits, wy);
356 BitMapView exp = mexp.make_view(bits, wexp);
357
358 (x.*f)(y);
359
360 EXPECT_TRUE(exp.is_same(x));
361 check_tail_unmodified(mx, bits, wx);
362 }
363
check_mod_setop_with_result(bool (BitMap::* f)(const BitMap &),idx_t bits,bm_word_t wx,bm_word_t wy,bm_word_t wexp)364 static void check_mod_setop_with_result(bool (BitMap::*f)(const BitMap&),
365 idx_t bits,
366 bm_word_t wx,
367 bm_word_t wy,
368 bm_word_t wexp) {
369 BitMapMemory mx(bits);
370 BitMapMemory my(bits);
371 BitMapMemory mexp(bits);
372
373 BitMapView x = mx.make_view(bits, wx);
374 BitMapView y = my.make_view(bits, wy);
375 BitMapView exp = mexp.make_view(bits, wexp);
376
377 bool value = (x.*f)(y);
378 EXPECT_EQ(value, wx != wexp);
379
380 EXPECT_TRUE(exp.is_same(x));
381 check_tail_unmodified(mx, bits, wx);
382 }
383
384 #define CHECK_MOD_SETOP_AUX(checker, name, x, y, exp) \
385 TEST(BitMap, name ## __ ## x ## _ ## y) { \
386 checker(&BitMap::name, aligned_size, \
387 x ## _bits, y ## _bits, exp ## _bits); \
388 checker(&BitMap::name, unaligned_size, \
389 x ## _bits, y ## _bits, exp ## _bits); \
390 }
391
392 #define CHECK_MOD_SETOP(name, x, y, exp) \
393 CHECK_MOD_SETOP_AUX(check_mod_setop, name, x, y, exp)
394
395 #define CHECK_MOD_SETOP_WITH_RESULT(name, x, y, exp) \
396 CHECK_MOD_SETOP_AUX(check_mod_setop_with_result, name, x, y, exp)
397
398 #define CHECK_MOD_SETOPS(name, x, y, exp) \
399 CHECK_MOD_SETOP(name, x, y, exp) \
400 CHECK_MOD_SETOP_WITH_RESULT(name ## _with_result, x, y, exp)
401
402 CHECK_MOD_SETOP(set_from, even, even, even)
403 CHECK_MOD_SETOP(set_from, even, odd, odd)
404 CHECK_MOD_SETOP(set_from, even, one, one)
405 CHECK_MOD_SETOP(set_from, even, zero, zero)
406
407 CHECK_MOD_SETOPS(set_union, even, even, even)
408 CHECK_MOD_SETOPS(set_union, even, odd, one)
409 CHECK_MOD_SETOPS(set_union, even, one, one)
410 CHECK_MOD_SETOPS(set_union, even, zero, even)
411
412 CHECK_MOD_SETOPS(set_difference, even, even, zero)
413 CHECK_MOD_SETOPS(set_difference, even, odd, even)
414 CHECK_MOD_SETOPS(set_difference, even, one, zero)
415 CHECK_MOD_SETOPS(set_difference, even, zero, even)
416
417 CHECK_MOD_SETOPS(set_intersection, even, even, even)
418 CHECK_MOD_SETOPS(set_intersection, even, odd, zero)
419 CHECK_MOD_SETOPS(set_intersection, even, one, even)
420 CHECK_MOD_SETOPS(set_intersection, even, zero, zero)
421
422