452 lines
17 KiB
C++
452 lines
17 KiB
C++
/*
|
|
* Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
|
|
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
|
*
|
|
* This code is free software; you can redistribute it and/or modify it
|
|
* under the terms of the GNU General Public License version 2 only, as
|
|
* published by the Free Software Foundation.
|
|
*
|
|
* This code is distributed in the hope that it will be useful, but WITHOUT
|
|
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
* version 2 for more details (a copy is included in the LICENSE file that
|
|
* accompanied this code).
|
|
*
|
|
* You should have received a copy of the GNU General Public License version
|
|
* 2 along with this work; if not, write to the Free Software Foundation,
|
|
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
|
*
|
|
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
|
|
* or visit www.oracle.com if you need additional information or have any
|
|
* questions.
|
|
*/
|
|
|
|
#include "precompiled.hpp"
|
|
#include "gc/shenandoah/shenandoahSimpleBitMap.hpp"
|
|
#include "gc/shenandoah/shenandoahSimpleBitMap.inline.hpp"
|
|
|
|
#include <iostream>
|
|
#include "utilities/ostream.hpp"
|
|
#include "utilities/vmassert_uninstall.hpp"
|
|
#include "utilities/vmassert_reinstall.hpp"
|
|
#include "unittest.hpp"
|
|
|
|
static bool _success;
|
|
static size_t _assertion_failures;
|
|
|
|
#define BitMapAssertEqual(a, b) ASSERT_EQ((a), (b)); if ((a) != (b)) { _assertion_failures++; }
|
|
|
|
class ShenandoahSimpleBitMapTest: public ::testing::Test {
|
|
protected:
|
|
|
|
static const ssize_t SMALL_BITMAP_SIZE = 512;
|
|
static const ssize_t LARGE_BITMAP_SIZE = 4096;
|
|
|
|
// set_bits[] is an array of indexes holding bits that are supposed to be set, in increasing order.
|
|
static void verifyBitMapState(ShenandoahSimpleBitMap& bm, ssize_t size, ssize_t set_bits[], ssize_t num_set_bits) {
|
|
// Verify number of bits
|
|
BitMapAssertEqual(bm.size(), size);
|
|
|
|
ssize_t set_bit_index = 0;
|
|
// Check that is_set(idx) for every possible idx
|
|
for (ssize_t i = 0; i < size; i++) {
|
|
bool is_set = bm.is_set(i);
|
|
bool intended_value = false;;
|
|
if (set_bit_index < num_set_bits) {
|
|
if (set_bits[set_bit_index] == i) {
|
|
intended_value = true;
|
|
set_bit_index++;
|
|
}
|
|
} else {
|
|
// If we've exhausted set_bits array, there should be no more set_bits
|
|
BitMapAssertEqual(is_set, false);
|
|
BitMapAssertEqual(set_bit_index, num_set_bits);
|
|
}
|
|
BitMapAssertEqual(is_set, intended_value);
|
|
}
|
|
BitMapAssertEqual(set_bit_index, num_set_bits);
|
|
|
|
// Check that bits_at(array_idx) matches intended value for every valid array_idx value
|
|
set_bit_index = 0;
|
|
ssize_t alignment = bm.alignment();
|
|
for (ssize_t i = 0; i < size; i += alignment) {
|
|
size_t bits = bm.bits_at(i);
|
|
for (ssize_t b = 0; b < alignment; b++) {
|
|
ssize_t bit_value = i + b;
|
|
bool intended_value = false;;
|
|
if (set_bit_index < num_set_bits) {
|
|
if (set_bits[set_bit_index] == bit_value) {
|
|
intended_value = true;
|
|
set_bit_index++;
|
|
}
|
|
}
|
|
size_t bit_mask = ((size_t) 0x01) << b;
|
|
bool is_set = (bits & bit_mask) != 0;
|
|
BitMapAssertEqual(is_set, intended_value);
|
|
}
|
|
}
|
|
|
|
// Make sure find_first_set_bit() works correctly
|
|
ssize_t probe_point = 0;
|
|
for (ssize_t i = 0; i < num_set_bits; i++) {
|
|
ssize_t next_expected_bit = set_bits[i];
|
|
probe_point = bm.find_first_set_bit(probe_point);
|
|
BitMapAssertEqual(probe_point, next_expected_bit);
|
|
probe_point++; // Prepare to look beyond the most recent bit.
|
|
}
|
|
if (probe_point < size) {
|
|
probe_point = bm.find_first_set_bit(probe_point);
|
|
BitMapAssertEqual(probe_point, size); // Verify that last failed search returns sentinel value: num bits in bit map
|
|
}
|
|
|
|
// Confirm that find_first_set_bit() with a bounded search space works correctly
|
|
// Limit this search to the first 3/4 of the full bit map
|
|
ssize_t boundary_idx = 3 * size / 4;
|
|
probe_point = 0;
|
|
for (ssize_t i = 0; i < num_set_bits; i++) {
|
|
ssize_t next_expected_bit = set_bits[i];
|
|
if (next_expected_bit >= boundary_idx) {
|
|
break;
|
|
} else {
|
|
probe_point = bm.find_first_set_bit(probe_point, boundary_idx);
|
|
BitMapAssertEqual(probe_point, next_expected_bit);
|
|
probe_point++; // Prepare to look beyond the most recent bit.
|
|
}
|
|
}
|
|
if (probe_point < boundary_idx) {
|
|
// In case there are no set bits in the last 1/4 of bit map, confirm that last failed search returns sentinel: boundary_idx
|
|
probe_point = bm.find_first_set_bit(probe_point, boundary_idx);
|
|
BitMapAssertEqual(probe_point, boundary_idx);
|
|
}
|
|
|
|
// Make sure find_last_set_bit() works correctly
|
|
probe_point = size - 1;
|
|
for (ssize_t i = num_set_bits - 1; i >= 0; i--) {
|
|
ssize_t next_expected_bit = set_bits[i];
|
|
probe_point = bm.find_last_set_bit(probe_point);
|
|
BitMapAssertEqual(probe_point, next_expected_bit);
|
|
probe_point--; // Prepare to look before the most recent bit.
|
|
}
|
|
if (probe_point >= 0) {
|
|
probe_point = bm.find_last_set_bit(probe_point);
|
|
BitMapAssertEqual(probe_point, (ssize_t) -1); // Verify that last failed search returns sentinel value: -1
|
|
}
|
|
|
|
// Confirm that find_last_set_bit() with a bounded search space works correctly
|
|
// Limit this search to the last 3/4 of the full bit map
|
|
boundary_idx = size / 4;
|
|
probe_point = size - 1;
|
|
for (ssize_t i = num_set_bits - 1; i >= 0; i--) {
|
|
ssize_t next_expected_bit = set_bits[i];
|
|
if (next_expected_bit > boundary_idx) {
|
|
probe_point = bm.find_last_set_bit(boundary_idx, probe_point);
|
|
BitMapAssertEqual(probe_point, next_expected_bit);
|
|
probe_point--;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
if (probe_point > boundary_idx) {
|
|
probe_point = bm.find_last_set_bit(boundary_idx, probe_point);
|
|
// Verify that last failed search returns sentinel value: boundary_idx
|
|
BitMapAssertEqual(probe_point, boundary_idx);
|
|
}
|
|
|
|
// What's the longest cluster of consecutive bits
|
|
ssize_t previous_value = -2;
|
|
ssize_t longest_run = 0;
|
|
ssize_t current_run = 0;
|
|
for (ssize_t i = 0; i < num_set_bits; i++) {
|
|
ssize_t next_expected_bit = set_bits[i];
|
|
if (next_expected_bit == previous_value + 1) {
|
|
current_run++;
|
|
} else {
|
|
previous_value = next_expected_bit;
|
|
current_run = 1;
|
|
}
|
|
if (current_run > longest_run) {
|
|
longest_run = current_run;
|
|
}
|
|
previous_value = next_expected_bit;
|
|
}
|
|
|
|
// Confirm that find_first_consecutive_set_bits() works for each cluster size known to have at least one match
|
|
for (ssize_t cluster_size = 1; cluster_size <= longest_run; cluster_size++) {
|
|
// Verify that find_first_consecutive_set_bits() works
|
|
ssize_t bit_idx = 0;
|
|
ssize_t probe_point = 0;
|
|
while ((probe_point <= size - cluster_size) && (bit_idx <= num_set_bits - cluster_size)) {
|
|
bool cluster_found = false;
|
|
while (!cluster_found && (bit_idx + cluster_size <= num_set_bits)) {
|
|
cluster_found = true;
|
|
for (ssize_t i = 1; i < cluster_size; i++) {
|
|
if (set_bits[bit_idx] + i != set_bits[bit_idx + i]) {
|
|
cluster_found = false;
|
|
bit_idx++;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if (cluster_found) {
|
|
ssize_t next_expected_cluster = set_bits[bit_idx];
|
|
ssize_t orig_probe_point = probe_point;
|
|
probe_point = bm.find_first_consecutive_set_bits(orig_probe_point, cluster_size);
|
|
BitMapAssertEqual(next_expected_cluster, probe_point);
|
|
probe_point++;
|
|
bit_idx++;
|
|
} else {
|
|
bit_idx++;
|
|
break;
|
|
}
|
|
}
|
|
if (probe_point < size) {
|
|
// Confirm that the last request, which fails to find a cluster, returns sentinel value: num_bits
|
|
probe_point = bm.find_first_consecutive_set_bits(probe_point, cluster_size);
|
|
BitMapAssertEqual(probe_point, size);
|
|
}
|
|
|
|
// Repeat the above experiment, using 3/4 size as the search boundary_idx
|
|
bit_idx = 0;
|
|
probe_point = 0;
|
|
boundary_idx = 4 * size / 4;
|
|
while ((probe_point <= boundary_idx - cluster_size) && (bit_idx <= num_set_bits - cluster_size)) {
|
|
bool cluster_found = false;
|
|
while (!cluster_found && (bit_idx + cluster_size <= num_set_bits)) {
|
|
cluster_found = true;
|
|
for (int i = 1; i < cluster_size; i++) {
|
|
if (set_bits[bit_idx] + i != set_bits[bit_idx + i]) {
|
|
cluster_found = false;
|
|
bit_idx++;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if (cluster_found) {
|
|
ssize_t next_expected_cluster = set_bits[bit_idx];
|
|
probe_point = bm.find_first_consecutive_set_bits(probe_point, boundary_idx, cluster_size);
|
|
BitMapAssertEqual(next_expected_cluster, probe_point);
|
|
probe_point++;
|
|
bit_idx++;
|
|
} else {
|
|
bit_idx++;
|
|
}
|
|
}
|
|
if (probe_point < boundary_idx) {
|
|
// Confirm that the last request, which fails to find a cluster, returns sentinel value: boundary_idx
|
|
probe_point = bm.find_first_consecutive_set_bits(probe_point, boundary_idx, cluster_size);
|
|
BitMapAssertEqual(probe_point, boundary_idx);
|
|
}
|
|
|
|
// Verify that find_last_consecutive_set_bits() works
|
|
bit_idx = num_set_bits - 1;
|
|
probe_point = size - 1;
|
|
// Iterate over all set bits in reverse order
|
|
while (bit_idx + 1 >= cluster_size) {
|
|
bool cluster_found = true;
|
|
for (int i = 1; i < cluster_size; i++) {
|
|
if (set_bits[bit_idx] - i != set_bits[bit_idx - i]) {
|
|
cluster_found = false;
|
|
break;
|
|
}
|
|
}
|
|
if (cluster_found) {
|
|
ssize_t next_expected_cluster = set_bits[bit_idx] + 1 - cluster_size;
|
|
probe_point = bm.find_last_consecutive_set_bits(probe_point, cluster_size);
|
|
BitMapAssertEqual(next_expected_cluster, probe_point);
|
|
probe_point = probe_point + cluster_size - 2;
|
|
bit_idx--;
|
|
} else {
|
|
bit_idx--;
|
|
}
|
|
}
|
|
if (probe_point >= 0) {
|
|
// Confirm that the last request, which fails to find a cluster, returns sentinel value: boundary_idx
|
|
probe_point = bm.find_last_consecutive_set_bits(boundary_idx, probe_point, cluster_size);
|
|
BitMapAssertEqual(probe_point, (ssize_t) boundary_idx);
|
|
}
|
|
|
|
// Verify that find_last_consecutive_set_bits() works with the search range bounded at 1/4 size
|
|
bit_idx = num_set_bits - 1;
|
|
probe_point = size - 1;
|
|
boundary_idx = size / 4;
|
|
while (bit_idx + 1 >= cluster_size) {
|
|
bool cluster_found = true;
|
|
for (int i = 1; i < cluster_size; i++) {
|
|
if (set_bits[bit_idx] - i != set_bits[bit_idx - i]) {
|
|
cluster_found = false;
|
|
break;
|
|
}
|
|
}
|
|
if (cluster_found && (set_bits[bit_idx] + 1 - cluster_size > boundary_idx)) {
|
|
ssize_t next_expected_cluster = set_bits[bit_idx] + 1 - cluster_size;
|
|
probe_point = bm.find_last_consecutive_set_bits(boundary_idx, probe_point, cluster_size);
|
|
BitMapAssertEqual(next_expected_cluster, probe_point);
|
|
probe_point = probe_point + cluster_size - 2;
|
|
bit_idx--;
|
|
} else if (set_bits[bit_idx] + 1 - cluster_size <= boundary_idx) {
|
|
break;
|
|
} else {
|
|
bit_idx--;
|
|
}
|
|
}
|
|
if (probe_point > boundary_idx) {
|
|
// Confirm that the last request, which fails to find a cluster, returns sentinel value: boundary_idx
|
|
probe_point = bm.find_last_consecutive_set_bits(boundary_idx, probe_point, cluster_size);
|
|
BitMapAssertEqual(probe_point, boundary_idx);
|
|
}
|
|
}
|
|
|
|
// Confirm that find_first_consecutive_set_bits() works for a cluster size known not to have any matches
|
|
probe_point = bm.find_first_consecutive_set_bits(0, longest_run + 1);
|
|
BitMapAssertEqual(probe_point, size); // Confirm: failed search returns sentinel: size
|
|
|
|
probe_point = bm.find_last_consecutive_set_bits(size - 1, longest_run + 1);
|
|
BitMapAssertEqual(probe_point, (ssize_t) -1); // Confirm: failed search returns sentinel: -1
|
|
|
|
boundary_idx = 3 * size / 4;
|
|
probe_point = bm.find_first_consecutive_set_bits(0, boundary_idx, longest_run + 1);
|
|
BitMapAssertEqual(probe_point, boundary_idx); // Confirm: failed search returns sentinel: boundary_idx
|
|
|
|
boundary_idx = size / 4;
|
|
probe_point = bm.find_last_consecutive_set_bits(boundary_idx, size - 1, longest_run + 1);
|
|
BitMapAssertEqual(probe_point, boundary_idx); // Confirm: failed search returns sentinel: boundary_idx
|
|
}
|
|
|
|
public:
|
|
|
|
static bool run_test() {
|
|
|
|
_success = false;
|
|
_assertion_failures = 0;
|
|
|
|
ShenandoahSimpleBitMap bm_small(SMALL_BITMAP_SIZE);
|
|
ShenandoahSimpleBitMap bm_large(LARGE_BITMAP_SIZE);
|
|
|
|
// Initial state of each bitmap is all bits are clear. Confirm this:
|
|
ssize_t set_bits_0[1] = { 0 };
|
|
verifyBitMapState(bm_small, SMALL_BITMAP_SIZE, set_bits_0, 0);
|
|
verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_0, 0);
|
|
|
|
bm_small.set_bit(5);
|
|
bm_small.set_bit(63);
|
|
bm_small.set_bit(128);
|
|
ssize_t set_bits_1[3] = { 5, 63, 128 };
|
|
verifyBitMapState(bm_small, SMALL_BITMAP_SIZE, set_bits_1, 3);
|
|
|
|
bm_large.set_bit(5);
|
|
bm_large.set_bit(63);
|
|
bm_large.set_bit(128);
|
|
verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_1, 3);
|
|
|
|
// Test some consecutive bits
|
|
bm_small.set_bit(140);
|
|
bm_small.set_bit(141);
|
|
bm_small.set_bit(142);
|
|
|
|
bm_small.set_bit(253);
|
|
bm_small.set_bit(254);
|
|
bm_small.set_bit(255);
|
|
|
|
bm_small.set_bit(271);
|
|
bm_small.set_bit(272);
|
|
|
|
bm_small.set_bit(320);
|
|
bm_small.set_bit(321);
|
|
bm_small.set_bit(322);
|
|
|
|
bm_small.set_bit(361);
|
|
|
|
ssize_t set_bits_2[15] = { 5, 63, 128, 140, 141, 142, 253, 254, 255, 271, 272, 320, 321, 322, 361 };
|
|
verifyBitMapState(bm_small, SMALL_BITMAP_SIZE, set_bits_2, 15);
|
|
|
|
bm_large.set_bit(140);
|
|
bm_large.set_bit(141);
|
|
bm_large.set_bit(142);
|
|
|
|
bm_large.set_bit(1021);
|
|
bm_large.set_bit(1022);
|
|
bm_large.set_bit(1023);
|
|
|
|
bm_large.set_bit(1051);
|
|
|
|
bm_large.set_bit(1280);
|
|
bm_large.set_bit(1281);
|
|
bm_large.set_bit(1282);
|
|
|
|
bm_large.set_bit(1300);
|
|
bm_large.set_bit(1301);
|
|
bm_large.set_bit(1302);
|
|
|
|
ssize_t set_bits_3[16] = { 5, 63, 128, 140, 141, 142, 1021, 1022, 1023, 1051, 1280, 1281, 1282, 1300, 1301, 1302 };
|
|
verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_3, 16);
|
|
|
|
// Test clear_bit
|
|
bm_small.clear_bit(141);
|
|
bm_small.clear_bit(253);
|
|
ssize_t set_bits_4[13] = { 5, 63, 128, 140, 142, 254, 255, 271, 272, 320, 321, 322, 361 };
|
|
verifyBitMapState(bm_small, SMALL_BITMAP_SIZE, set_bits_4, 13);
|
|
|
|
bm_large.clear_bit(5);
|
|
bm_large.clear_bit(63);
|
|
bm_large.clear_bit(128);
|
|
bm_large.clear_bit(141);
|
|
ssize_t set_bits_5[12] = { 140, 142, 1021, 1022, 1023, 1051, 1280, 1281, 1282, 1300, 1301, 1302 };
|
|
verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_5, 12);
|
|
|
|
// Look for large island of contiguous surrounded by smaller islands of contiguous
|
|
bm_large.set_bit(1024);
|
|
bm_large.set_bit(1025); // size-5 island from 1021 to 1025
|
|
bm_large.set_bit(1027);
|
|
bm_large.set_bit(1028);
|
|
bm_large.set_bit(1029);
|
|
bm_large.set_bit(1030);
|
|
bm_large.set_bit(1031);
|
|
bm_large.set_bit(1032); // size-6 island from 1027 to 1032
|
|
bm_large.set_bit(1034);
|
|
bm_large.set_bit(1035);
|
|
bm_large.set_bit(1036); // size-3 island from 1034 to 1036
|
|
ssize_t set_bits_6[23] = { 140, 142, 1021, 1022, 1023, 1024, 1025, 1027, 1028, 1029, 1030,
|
|
1031, 1032, 1034, 1035, 1036, 1051, 1280, 1281, 1282, 1300, 1301, 1302 };
|
|
verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_6, 23);
|
|
|
|
// Test that entire bitmap word (from 1024 to 1088) is 1's
|
|
ssize_t set_bits_7[76];
|
|
set_bits_7[0] = 140;
|
|
set_bits_7[1] = 142;
|
|
set_bits_7[2] = 1021;
|
|
set_bits_7[3] = 1022;
|
|
set_bits_7[4] = 1023;
|
|
size_t bit_idx = 5;
|
|
for (ssize_t i = 1024; i <= 1088; i++) {
|
|
bm_large.set_bit(i);
|
|
set_bits_7[bit_idx++] = i;
|
|
}
|
|
set_bits_7[bit_idx++] = 1280;
|
|
set_bits_7[bit_idx++] = 1281;
|
|
set_bits_7[bit_idx++] = 1282;
|
|
set_bits_7[bit_idx++] = 1300;
|
|
set_bits_7[bit_idx++] = 1301;
|
|
set_bits_7[bit_idx++] = 1302;
|
|
verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_7, bit_idx);
|
|
|
|
// Test clear_all()
|
|
bm_small.clear_all();
|
|
bm_large.clear_all();
|
|
|
|
verifyBitMapState(bm_small, SMALL_BITMAP_SIZE, set_bits_0, 0);
|
|
verifyBitMapState(bm_large, LARGE_BITMAP_SIZE, set_bits_0, 0);
|
|
|
|
_success = true;
|
|
return true;
|
|
}
|
|
|
|
};
|
|
|
|
TEST(BasicShenandoahSimpleBitMapTest, minimum_test) {
|
|
|
|
bool result = ShenandoahSimpleBitMapTest::run_test();
|
|
ASSERT_EQ(result, true);
|
|
ASSERT_EQ(_success, true);
|
|
ASSERT_EQ(_assertion_failures, (size_t) 0);
|
|
}
|