jdk

1
/*
2
 * Copyright Amazon.com Inc. 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 "gc/shenandoah/shenandoahSimpleBitMap.hpp"
26
#include "gc/shenandoah/shenandoahSimpleBitMap.inline.hpp"
27

28
#include <iostream>
29
#include "utilities/ostream.hpp"
30
#include "utilities/vmassert_uninstall.hpp"
31
#include "utilities/vmassert_reinstall.hpp"
32
#include "unittest.hpp"
33

34
static bool _success;
35
static size_t _assertion_failures;
36

37
#define BitMapAssertEqual(a, b)  ASSERT_EQ((a), (b)); if ((a) != (b)) { _assertion_failures++; }
38

39
class ShenandoahSimpleBitMapTest: public ::testing::Test {
40
protected:
41

42
  static const ssize_t SMALL_BITMAP_SIZE =  512;
43
  static const ssize_t LARGE_BITMAP_SIZE = 4096;
44

45
  // set_bits[] is an array of indexes holding bits that are supposed to be set, in increasing order.
46
  static void verifyBitMapState(ShenandoahSimpleBitMap& bm, ssize_t size, ssize_t set_bits[], ssize_t num_set_bits) {
47
    // Verify number of bits
48
    BitMapAssertEqual(bm.size(), size);
49

50
    ssize_t set_bit_index = 0;
51
    // Check that is_set(idx) for every possible idx
52
    for (ssize_t i = 0; i < size; i++) {
53
      bool is_set = bm.is_set(i);
54
      bool intended_value = false;;
55
      if (set_bit_index < num_set_bits) {
56
        if (set_bits[set_bit_index] == i) {
57
          intended_value = true;
58
          set_bit_index++;
59
        }
60
      } else {
61
        // If we've exhausted set_bits array, there should be no more set_bits
62
        BitMapAssertEqual(is_set, false);
63
        BitMapAssertEqual(set_bit_index, num_set_bits);
64
      }
65
      BitMapAssertEqual(is_set, intended_value);
66
    }
67
    BitMapAssertEqual(set_bit_index, num_set_bits);
68

69
    // Check that bits_at(array_idx) matches intended value for every valid array_idx value
70
    set_bit_index = 0;
71
    ssize_t alignment = bm.alignment();
72
    for (ssize_t i = 0; i < size; i += alignment) {
73
      size_t bits = bm.bits_at(i);
74
      for (ssize_t b = 0; b < alignment; b++) {
75
        ssize_t bit_value = i + b;
76
        bool intended_value = false;;
77
        if (set_bit_index < num_set_bits) {
78
          if (set_bits[set_bit_index] == bit_value) {
79
            intended_value = true;
80
            set_bit_index++;
81
          }
82
        }
83
        size_t bit_mask = ((size_t) 0x01) << b;
84
        bool is_set = (bits & bit_mask) != 0;
85
        BitMapAssertEqual(is_set, intended_value);
86
      }
87
    }
88

89
    // Make sure find_first_set_bit() works correctly
90
    ssize_t probe_point = 0;
91
    for (ssize_t i = 0; i < num_set_bits; i++) {
92
      ssize_t next_expected_bit = set_bits[i];
93
      probe_point = bm.find_first_set_bit(probe_point);
94
      BitMapAssertEqual(probe_point, next_expected_bit);
95
      probe_point++;            // Prepare to look beyond the most recent bit.
96
    }
97
    if (probe_point < size) {
98
      probe_point = bm.find_first_set_bit(probe_point);
99
      BitMapAssertEqual(probe_point, size); // Verify that last failed search returns sentinel value: num bits in bit map
100
    }
101

102
    // Confirm that find_first_set_bit() with a bounded search space works correctly
103
    // Limit this search to the first 3/4 of the full bit map
104
    ssize_t boundary_idx = 3 * size / 4;
105
    probe_point = 0;
106
    for (ssize_t i = 0; i < num_set_bits; i++) {
107
      ssize_t next_expected_bit = set_bits[i];
108
      if (next_expected_bit >= boundary_idx) {
109
        break;
110
      } else {
111
        probe_point = bm.find_first_set_bit(probe_point, boundary_idx);
112
        BitMapAssertEqual(probe_point, next_expected_bit);
113
        probe_point++;            // Prepare to look beyond the most recent bit.
114
      }
115
    }
116
    if (probe_point < boundary_idx) {
117
      // In case there are no set bits in the last 1/4 of bit map, confirm that last failed search returns sentinel: boundary_idx
118
      probe_point = bm.find_first_set_bit(probe_point, boundary_idx);
119
      BitMapAssertEqual(probe_point, boundary_idx);
120
    }
121

122
    // Make sure find_last_set_bit() works correctly
123
    probe_point = size - 1;
124
    for (ssize_t i = num_set_bits - 1; i >= 0; i--) {
125
      ssize_t next_expected_bit = set_bits[i];
126
      probe_point = bm.find_last_set_bit(probe_point);
127
      BitMapAssertEqual(probe_point, next_expected_bit);
128
      probe_point--;            // Prepare to look before the most recent bit.
129
    }
130
    if (probe_point >= 0) {
131
      probe_point = bm.find_last_set_bit(probe_point);
132
      BitMapAssertEqual(probe_point, (ssize_t) -1); // Verify that last failed search returns sentinel value: -1
133
    }
134

135
    // Confirm that find_last_set_bit() with a bounded search space works correctly
136
    // Limit this search to the last 3/4 of the full bit map
137
    boundary_idx = size / 4;
138
    probe_point = size - 1;
139
    for (ssize_t i = num_set_bits - 1; i >= 0; i--) {
140
      ssize_t next_expected_bit = set_bits[i];
141
      if (next_expected_bit > boundary_idx) {
142
        probe_point = bm.find_last_set_bit(boundary_idx, probe_point);
143
        BitMapAssertEqual(probe_point, next_expected_bit);
144
        probe_point--;
145
      } else {
146
        break;
147
      }
148
    }
149
    if (probe_point > boundary_idx) {
150
      probe_point = bm.find_last_set_bit(boundary_idx, probe_point);
151
        // Verify that last failed search returns sentinel value: boundary_idx
152
      BitMapAssertEqual(probe_point, boundary_idx);
153
    }
154

155
    // What's the longest cluster of consecutive bits
156
    ssize_t previous_value = -2;
157
    ssize_t longest_run = 0;
158
    ssize_t current_run = 0;
159
    for (ssize_t i = 0; i < num_set_bits; i++) {
160
      ssize_t next_expected_bit = set_bits[i];
161
      if (next_expected_bit == previous_value + 1) {
162
        current_run++;
163
      } else {
164
        previous_value = next_expected_bit;
165
        current_run = 1;
166
      }
167
      if (current_run > longest_run) {
168
        longest_run = current_run;
169
      }
170
      previous_value = next_expected_bit;
171
    }
172

173
    // Confirm that find_first_consecutive_set_bits() works for each cluster size known to have at least one match
174
    for (ssize_t cluster_size = 1; cluster_size <= longest_run; cluster_size++) {
175
      // Verify that find_first_consecutive_set_bits() works
176
      ssize_t bit_idx = 0;
177
      ssize_t probe_point = 0;
178
      while ((probe_point <= size - cluster_size) && (bit_idx <= num_set_bits - cluster_size)) {
179
        bool cluster_found = false;
180
        while (!cluster_found && (bit_idx + cluster_size <= num_set_bits)) {
181
          cluster_found = true;
182
          for (ssize_t i = 1; i < cluster_size; i++) {
183
            if (set_bits[bit_idx] + i != set_bits[bit_idx + i]) {
184
              cluster_found = false;
185
              bit_idx++;
186
              break;
187
            }
188
          }
189
        }
190
        if (cluster_found) {
191
          ssize_t next_expected_cluster = set_bits[bit_idx];
192
          ssize_t orig_probe_point = probe_point;
193
          probe_point = bm.find_first_consecutive_set_bits(orig_probe_point, cluster_size);
194
          BitMapAssertEqual(next_expected_cluster, probe_point);
195
          probe_point++;
196
          bit_idx++;
197
        } else {
198
          bit_idx++;
199
          break;
200
        }
201
      }
202
      if (probe_point < size) {
203
        // Confirm that the last request, which fails to find a cluster, returns sentinel value: num_bits
204
        probe_point = bm.find_first_consecutive_set_bits(probe_point, cluster_size);
205
        BitMapAssertEqual(probe_point, size);
206
      }
207

208
      // Repeat the above experiment, using 3/4 size as the search boundary_idx
209
      bit_idx = 0;
210
      probe_point = 0;
211
      boundary_idx = 4 * size / 4;
212
      while ((probe_point <= boundary_idx - cluster_size) && (bit_idx <= num_set_bits - cluster_size)) {
213
        bool cluster_found = false;
214
        while (!cluster_found && (bit_idx + cluster_size <= num_set_bits)) {
215
          cluster_found = true;
216
          for (int i = 1; i < cluster_size; i++) {
217
            if (set_bits[bit_idx] + i != set_bits[bit_idx + i]) {
218
              cluster_found = false;
219
              bit_idx++;
220
              break;
221
            }
222
          }
223
        }
224
        if (cluster_found) {
225
          ssize_t next_expected_cluster = set_bits[bit_idx];
226
          probe_point = bm.find_first_consecutive_set_bits(probe_point, boundary_idx, cluster_size);
227
          BitMapAssertEqual(next_expected_cluster, probe_point);
228
          probe_point++;
229
          bit_idx++;
230
        } else {
231
          bit_idx++;
232
        }
233
      }
234
      if (probe_point < boundary_idx) {
235
        // Confirm that the last request, which fails to find a cluster, returns sentinel value: boundary_idx
236
        probe_point = bm.find_first_consecutive_set_bits(probe_point, boundary_idx, cluster_size);
237
        BitMapAssertEqual(probe_point, boundary_idx);
238
      }
239

240
      // Verify that find_last_consecutive_set_bits() works
241
      bit_idx = num_set_bits - 1;
242
      probe_point = size - 1;
243
      // Iterate over all set bits in reverse order
244
      while (bit_idx + 1 >= cluster_size) {
245
        bool cluster_found = true;
246
        for (int i = 1; i < cluster_size; i++) {
247
          if (set_bits[bit_idx] - i != set_bits[bit_idx - i]) {
248
            cluster_found = false;
249
            break;
250
          }
251
        }
252
        if (cluster_found) {
253
          ssize_t next_expected_cluster = set_bits[bit_idx] + 1 - cluster_size;
254
          probe_point = bm.find_last_consecutive_set_bits(probe_point, cluster_size);
255
          BitMapAssertEqual(next_expected_cluster, probe_point);
256
          probe_point = probe_point + cluster_size - 2;
257
          bit_idx--;
258
        } else {
259
          bit_idx--;
260
        }
261
      }
262
      if (probe_point >= 0) {
263
        // Confirm that the last request, which fails to find a cluster, returns sentinel value: boundary_idx
264
        probe_point = bm.find_last_consecutive_set_bits(boundary_idx, probe_point, cluster_size);
265
        BitMapAssertEqual(probe_point, (ssize_t) boundary_idx);
266
      }
267

268
      // Verify that find_last_consecutive_set_bits() works with the search range bounded at 1/4 size
269
      bit_idx = num_set_bits - 1;
270
      probe_point = size - 1;
271
      boundary_idx = size / 4;
272
      while (bit_idx + 1 >= cluster_size) {
273
        bool cluster_found = true;
274
        for (int i = 1; i < cluster_size; i++) {
275
          if (set_bits[bit_idx] - i != set_bits[bit_idx - i]) {
276
            cluster_found = false;
277
            break;
278
          }
279
        }
280
        if (cluster_found && (set_bits[bit_idx] + 1 - cluster_size > boundary_idx)) {
281
          ssize_t next_expected_cluster = set_bits[bit_idx] + 1 - cluster_size;
282
          probe_point = bm.find_last_consecutive_set_bits(boundary_idx, probe_point, cluster_size);
283
          BitMapAssertEqual(next_expected_cluster, probe_point);
284
          probe_point = probe_point + cluster_size - 2;
285
          bit_idx--;
286
        } else if (set_bits[bit_idx] + 1 - cluster_size <= boundary_idx) {
287
          break;
288
        } else {
289
          bit_idx--;
290
        }
291
      }
292
      if (probe_point > boundary_idx) {
293
        // Confirm that the last request, which fails to find a cluster, returns sentinel value: boundary_idx
294
        probe_point = bm.find_last_consecutive_set_bits(boundary_idx, probe_point, cluster_size);
295
        BitMapAssertEqual(probe_point, boundary_idx);
296
      }
297
    }
298

299
    // Confirm that find_first_consecutive_set_bits() works for a cluster size known not to have any matches
300
    probe_point = bm.find_first_consecutive_set_bits(0, longest_run + 1);
301
    BitMapAssertEqual(probe_point, size);  // Confirm: failed search returns sentinel: size
302

303
    probe_point = bm.find_last_consecutive_set_bits(size - 1, longest_run + 1);
304
    BitMapAssertEqual(probe_point, (ssize_t) -1);    // Confirm: failed search returns sentinel: -1
305

306
    boundary_idx = 3 * size / 4;
307
    probe_point = bm.find_first_consecutive_set_bits(0, boundary_idx, longest_run + 1);
308
    BitMapAssertEqual(probe_point, boundary_idx); // Confirm: failed search returns sentinel: boundary_idx
309

310
    boundary_idx = size / 4;
311
    probe_point = bm.find_last_consecutive_set_bits(boundary_idx, size - 1, longest_run + 1);
312
    BitMapAssertEqual(probe_point, boundary_idx);           // Confirm: failed search returns sentinel: boundary_idx
313
  }
314

315
public:
316

317
  static bool run_test() {
318

319
    _success = false;
320
    _assertion_failures = 0;
321

322
    ShenandoahSimpleBitMap bm_small(SMALL_BITMAP_SIZE);
323
    ShenandoahSimpleBitMap bm_large(LARGE_BITMAP_SIZE);
324

325
    // Initial state of each bitmap is all bits are clear.  Confirm this:
326
    ssize_t set_bits_0[1] = { 0 };
327
    verifyBitMapState(bm_small, SMALL_BITMAP_SIZE, set_bits_0, 0);
328
    verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_0, 0);
329

330
    bm_small.set_bit(5);
331
    bm_small.set_bit(63);
332
    bm_small.set_bit(128);
333
    ssize_t set_bits_1[3] = { 5, 63, 128 };
334
    verifyBitMapState(bm_small, SMALL_BITMAP_SIZE, set_bits_1, 3);
335

336
    bm_large.set_bit(5);
337
    bm_large.set_bit(63);
338
    bm_large.set_bit(128);
339
    verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_1, 3);
340

341
    // Test some consecutive bits
342
    bm_small.set_bit(140);
343
    bm_small.set_bit(141);
344
    bm_small.set_bit(142);
345

346
    bm_small.set_bit(253);
347
    bm_small.set_bit(254);
348
    bm_small.set_bit(255);
349

350
    bm_small.set_bit(271);
351
    bm_small.set_bit(272);
352

353
    bm_small.set_bit(320);
354
    bm_small.set_bit(321);
355
    bm_small.set_bit(322);
356

357
    bm_small.set_bit(361);
358

359
    ssize_t set_bits_2[15] = { 5, 63, 128, 140, 141, 142, 253, 254, 255, 271, 272, 320, 321, 322, 361 };
360
    verifyBitMapState(bm_small, SMALL_BITMAP_SIZE, set_bits_2, 15);
361

362
    bm_large.set_bit(140);
363
    bm_large.set_bit(141);
364
    bm_large.set_bit(142);
365

366
    bm_large.set_bit(1021);
367
    bm_large.set_bit(1022);
368
    bm_large.set_bit(1023);
369

370
    bm_large.set_bit(1051);
371

372
    bm_large.set_bit(1280);
373
    bm_large.set_bit(1281);
374
    bm_large.set_bit(1282);
375

376
    bm_large.set_bit(1300);
377
    bm_large.set_bit(1301);
378
    bm_large.set_bit(1302);
379

380
    ssize_t set_bits_3[16] = { 5, 63, 128, 140, 141, 142, 1021, 1022, 1023, 1051, 1280, 1281, 1282, 1300, 1301, 1302 };
381
    verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_3, 16);
382

383
    // Test clear_bit
384
    bm_small.clear_bit(141);
385
    bm_small.clear_bit(253);
386
    ssize_t set_bits_4[13] = { 5, 63, 128, 140, 142, 254, 255, 271, 272, 320, 321, 322, 361 };
387
    verifyBitMapState(bm_small, SMALL_BITMAP_SIZE, set_bits_4, 13);
388

389
    bm_large.clear_bit(5);
390
    bm_large.clear_bit(63);
391
    bm_large.clear_bit(128);
392
    bm_large.clear_bit(141);
393
    ssize_t set_bits_5[12] = { 140, 142, 1021, 1022, 1023, 1051, 1280, 1281, 1282, 1300, 1301, 1302 };
394
    verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_5, 12);
395

396
    // Look for large island of contiguous surrounded by smaller islands of contiguous
397
    bm_large.set_bit(1024);
398
    bm_large.set_bit(1025);  // size-5 island from 1021 to 1025
399
    bm_large.set_bit(1027);
400
    bm_large.set_bit(1028);
401
    bm_large.set_bit(1029);
402
    bm_large.set_bit(1030);
403
    bm_large.set_bit(1031);
404
    bm_large.set_bit(1032);  // size-6 island from 1027 to 1032
405
    bm_large.set_bit(1034);
406
    bm_large.set_bit(1035);
407
    bm_large.set_bit(1036);  // size-3 island from 1034 to 1036
408
    ssize_t set_bits_6[23] = {  140,  142, 1021, 1022, 1023, 1024, 1025, 1027, 1028, 1029, 1030,
409
                               1031, 1032, 1034, 1035, 1036, 1051, 1280, 1281, 1282, 1300, 1301, 1302 };
410
    verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_6, 23);
411

412
    // Test that entire bitmap word (from 1024 to 1088) is 1's
413
    ssize_t set_bits_7[76];
414
    set_bits_7[0] = 140;
415
    set_bits_7[1] = 142;
416
    set_bits_7[2] = 1021;
417
    set_bits_7[3] = 1022;
418
    set_bits_7[4] = 1023;
419
    size_t bit_idx = 5;
420
    for (ssize_t i = 1024; i <= 1088; i++) {
421
      bm_large.set_bit(i);
422
      set_bits_7[bit_idx++] = i;
423
    }
424
    set_bits_7[bit_idx++] = 1280;
425
    set_bits_7[bit_idx++] = 1281;
426
    set_bits_7[bit_idx++] = 1282;
427
    set_bits_7[bit_idx++] = 1300;
428
    set_bits_7[bit_idx++] = 1301;
429
    set_bits_7[bit_idx++] = 1302;
430
    verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_7, bit_idx);
431

432
    // Test clear_all()
433
    bm_small.clear_all();
434
    bm_large.clear_all();
435

436
    verifyBitMapState(bm_small, SMALL_BITMAP_SIZE, set_bits_0, 0);
437
    verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_0, 0);
438

439
    _success = true;
440
    return true;
441
  }
442

443
};
444

445
TEST(BasicShenandoahSimpleBitMapTest, minimum_test) {
446

447
  bool result = ShenandoahSimpleBitMapTest::run_test();
448
  ASSERT_EQ(result, true);
449
  ASSERT_EQ(_success, true);
450
  ASSERT_EQ(_assertion_failures, (size_t) 0);
451
}
452