489 lines
15 KiB
C++
489 lines
15 KiB
C++
/*
|
||
* Copyright (c) 2021, 2024, Oracle and/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/g1/g1CardSet.inline.hpp"
|
||
#include "gc/g1/g1CardSetContainers.hpp"
|
||
#include "gc/g1/g1CardSetMemory.hpp"
|
||
#include "gc/g1/g1HeapRegionRemSet.hpp"
|
||
#include "gc/g1/g1MonotonicArenaFreePool.hpp"
|
||
#include "gc/shared/gcTraceTime.inline.hpp"
|
||
#include "gc/shared/workerThread.hpp"
|
||
#include "logging/log.hpp"
|
||
#include "memory/allocation.hpp"
|
||
#include "unittest.hpp"
|
||
#include "utilities/powerOfTwo.hpp"
|
||
|
||
class G1CardSetTest : public ::testing::Test {
|
||
|
||
class G1CountCardsClosure : public G1CardSet::CardClosure {
|
||
public:
|
||
size_t _num_cards;
|
||
|
||
G1CountCardsClosure() : _num_cards(0) { }
|
||
void do_card(uint region_idx, uint card_idx) override {
|
||
_num_cards++;
|
||
}
|
||
};
|
||
|
||
static WorkerThreads* _workers;
|
||
static uint _max_workers;
|
||
|
||
static WorkerThreads* workers() {
|
||
if (_workers == nullptr) {
|
||
_max_workers = os::processor_count();
|
||
_workers = new WorkerThreads("G1CardSetTest Workers", _max_workers);
|
||
_workers->initialize_workers();
|
||
_workers->set_active_workers(_max_workers);
|
||
}
|
||
return _workers;
|
||
}
|
||
|
||
// Check whether iteration agrees with the expected number of entries. If the
|
||
// add has been single-threaded, we can also check whether the occupied()
|
||
// (which is an estimate in that case) agrees.
|
||
static void check_iteration(G1CardSet* card_set,
|
||
const size_t expected,
|
||
const bool add_was_single_threaded = true);
|
||
|
||
public:
|
||
G1CardSetTest() { }
|
||
~G1CardSetTest() { }
|
||
|
||
static uint next_random(uint& seed, uint i) {
|
||
// Park–Miller random number generator
|
||
seed = (seed * 279470273u) % 0xfffffffb;
|
||
return (seed % i);
|
||
}
|
||
|
||
static void cardset_basic_test();
|
||
static void cardset_mt_test();
|
||
|
||
static void add_cards(G1CardSet* card_set, uint cards_per_region, uint* cards, uint num_cards, G1AddCardResult* results);
|
||
static void contains_cards(G1CardSet* card_set, uint cards_per_region, uint* cards, uint num_cards);
|
||
|
||
static void translate_cards(uint cards_per_region, uint region_idx, uint* cards, uint num_cards);
|
||
|
||
static void iterate_cards(G1CardSet* card_set, G1CardSet::CardClosure* cl);
|
||
};
|
||
|
||
WorkerThreads* G1CardSetTest::_workers = nullptr;
|
||
uint G1CardSetTest::_max_workers = 0;
|
||
|
||
void G1CardSetTest::add_cards(G1CardSet* card_set, uint cards_per_region, uint* cards, uint num_cards, G1AddCardResult* results) {
|
||
for (uint i = 0; i < num_cards; i++) {
|
||
|
||
uint region_idx = cards[i] / cards_per_region;
|
||
uint card_idx = cards[i] % cards_per_region;
|
||
|
||
G1AddCardResult res = card_set->add_card(region_idx, card_idx);
|
||
if (results != nullptr) {
|
||
ASSERT_TRUE(res == results[i]);
|
||
}
|
||
}
|
||
}
|
||
|
||
class G1CheckCardClosure : public G1CardSet::CardClosure {
|
||
G1CardSet* _card_set;
|
||
|
||
uint _cards_per_region;
|
||
uint* _cards_to_expect;
|
||
uint _num_cards;
|
||
|
||
bool _wrong_region_idx;
|
||
|
||
public:
|
||
G1CheckCardClosure(G1CardSet* card_set, uint cards_per_region, uint* cards_to_expect, uint num_cards) :
|
||
_card_set(card_set),
|
||
_cards_per_region(cards_per_region),
|
||
_cards_to_expect(cards_to_expect),
|
||
_num_cards(num_cards),
|
||
_wrong_region_idx(false) {
|
||
}
|
||
|
||
void do_card(uint region_idx, uint card_idx) override {
|
||
uint card = _cards_per_region * region_idx + card_idx;
|
||
for (uint i = 0; i < _num_cards; i++) {
|
||
if (_cards_to_expect[i] == card) {
|
||
_cards_to_expect[i] = (uint)-1;
|
||
}
|
||
}
|
||
}
|
||
|
||
bool all_found() const {
|
||
bool all_good = true;
|
||
for (uint i = 0; i < _num_cards; i++) {
|
||
if (_cards_to_expect[i] != (uint)-1) {
|
||
log_error(gc)("Could not find card %u in region %u",
|
||
_cards_to_expect[i] % _cards_per_region,
|
||
_cards_to_expect[i] / _cards_per_region);
|
||
all_good = false;
|
||
}
|
||
}
|
||
return all_good;
|
||
}
|
||
};
|
||
|
||
void G1CardSetTest::contains_cards(G1CardSet* card_set, uint cards_per_region, uint* cards, uint num_cards) {
|
||
for (uint i = 0; i < num_cards; i++) {
|
||
uint region_idx = cards[i] / cards_per_region;
|
||
uint card_idx = cards[i] % cards_per_region;
|
||
|
||
ASSERT_TRUE(card_set->contains_card(region_idx, card_idx));
|
||
}
|
||
|
||
G1CheckCardClosure cl(card_set, cards_per_region, cards, num_cards);
|
||
card_set->iterate_cards(cl);
|
||
|
||
ASSERT_TRUE(cl.all_found());
|
||
}
|
||
|
||
// Offsets the card indexes in the cards array by the region_idx.
|
||
void G1CardSetTest::translate_cards(uint cards_per_region, uint region_idx, uint* cards, uint num_cards) {
|
||
for (uint i = 0; i < num_cards; i++) {
|
||
cards[i] = cards_per_region * region_idx + cards[i];
|
||
}
|
||
}
|
||
|
||
class G1CountCardsOccupied : public G1CardSet::ContainerPtrClosure {
|
||
size_t _num_occupied;
|
||
|
||
public:
|
||
G1CountCardsOccupied() : _num_occupied(0) { }
|
||
|
||
void do_containerptr(uint region_idx, size_t num_occupied, G1CardSet::ContainerPtr container) override {
|
||
_num_occupied += num_occupied;
|
||
}
|
||
|
||
size_t num_occupied() const { return _num_occupied; }
|
||
};
|
||
|
||
void G1CardSetTest::check_iteration(G1CardSet* card_set, const size_t expected, const bool single_threaded) {
|
||
|
||
class CheckIterator : public G1CardSet::CardClosure {
|
||
public:
|
||
G1CardSet* _card_set;
|
||
size_t _num_found;
|
||
|
||
CheckIterator(G1CardSet* card_set) : _card_set(card_set), _num_found(0) { }
|
||
|
||
void do_card(uint region_idx, uint card_idx) override {
|
||
ASSERT_TRUE(_card_set->contains_card(region_idx, card_idx));
|
||
_num_found++;
|
||
}
|
||
} cl(card_set);
|
||
|
||
card_set->iterate_cards(cl);
|
||
|
||
ASSERT_TRUE(expected == cl._num_found);
|
||
// We can assert this only if we are single-threaded.
|
||
if (single_threaded) {
|
||
ASSERT_EQ(card_set->occupied(), cl._num_found);
|
||
}
|
||
}
|
||
|
||
void G1CardSetTest::cardset_basic_test() {
|
||
|
||
const uint CardsPerRegion = 2048;
|
||
const double FullCardSetThreshold = 0.8;
|
||
const double BitmapCoarsenThreshold = 0.9;
|
||
|
||
G1CardSetConfiguration config(28,
|
||
BitmapCoarsenThreshold,
|
||
8,
|
||
FullCardSetThreshold,
|
||
CardsPerRegion,
|
||
0);
|
||
G1CardSetFreePool free_pool(config.num_mem_object_types());
|
||
G1CardSetMemoryManager mm(&config, &free_pool);
|
||
|
||
{
|
||
G1CardSet card_set(&config, &mm);
|
||
|
||
uint cards1[] = { 1, 2, 3 };
|
||
G1AddCardResult results1[] = { Added, Added, Added };
|
||
translate_cards(CardsPerRegion, 99, cards1, ARRAY_SIZE(cards1));
|
||
add_cards(&card_set, CardsPerRegion, cards1, ARRAY_SIZE(cards1), results1);
|
||
contains_cards(&card_set, CardsPerRegion, cards1, ARRAY_SIZE(cards1));
|
||
ASSERT_TRUE(card_set.occupied() == ARRAY_SIZE(cards1));
|
||
|
||
G1CountCardsClosure count_cards;
|
||
card_set.iterate_cards(count_cards);
|
||
ASSERT_TRUE(count_cards._num_cards == ARRAY_SIZE(cards1));
|
||
|
||
check_iteration(&card_set, card_set.occupied());
|
||
|
||
card_set.clear();
|
||
ASSERT_TRUE(card_set.occupied() == 0);
|
||
|
||
check_iteration(&card_set, 0);
|
||
}
|
||
|
||
{
|
||
G1CardSet card_set(&config, &mm);
|
||
|
||
uint cards1[] = { 0, 2047, 17, 17 };
|
||
G1AddCardResult results1[] = { Added, Added, Added, Found };
|
||
translate_cards(CardsPerRegion, 100, cards1, ARRAY_SIZE(cards1));
|
||
add_cards(&card_set, CardsPerRegion, cards1, ARRAY_SIZE(cards1), results1);
|
||
// -1 because of the duplicate at the end.
|
||
contains_cards(&card_set, CardsPerRegion, cards1, ARRAY_SIZE(cards1) - 1);
|
||
ASSERT_TRUE(card_set.occupied() == ARRAY_SIZE(cards1) - 1);
|
||
|
||
G1CountCardsClosure count_cards;
|
||
card_set.iterate_cards(count_cards);
|
||
ASSERT_TRUE(count_cards._num_cards == ARRAY_SIZE(cards1) - 1);
|
||
|
||
check_iteration(&card_set, card_set.occupied());
|
||
|
||
card_set.clear();
|
||
ASSERT_TRUE(card_set.occupied() == 0);
|
||
}
|
||
|
||
{
|
||
G1CardSet card_set(&config, &mm);
|
||
|
||
uint cards1[] = { 0, 2047, 17, 18 /* for region 100 */,
|
||
1, 128, 35, 17 /* for region 990 */
|
||
};
|
||
translate_cards(CardsPerRegion, 100, &cards1[0], 4);
|
||
translate_cards(CardsPerRegion, 990, &cards1[4], 4);
|
||
|
||
add_cards(&card_set, CardsPerRegion, cards1, ARRAY_SIZE(cards1), nullptr);
|
||
contains_cards(&card_set, CardsPerRegion, cards1, ARRAY_SIZE(cards1));
|
||
ASSERT_TRUE(card_set.occupied() == ARRAY_SIZE(cards1));
|
||
|
||
G1CountCardsClosure count_cards;
|
||
card_set.iterate_cards(count_cards);
|
||
ASSERT_TRUE(count_cards._num_cards == ARRAY_SIZE(cards1));
|
||
|
||
check_iteration(&card_set, card_set.occupied());
|
||
|
||
card_set.clear();
|
||
ASSERT_TRUE(card_set.occupied() == 0);
|
||
}
|
||
|
||
{
|
||
G1CardSet card_set(&config, &mm);
|
||
|
||
uint cards1[100];
|
||
for (uint i = 0; i < ARRAY_SIZE(cards1); i++) {
|
||
cards1[i] = i + 3;
|
||
translate_cards(CardsPerRegion, i, &cards1[i], 1);
|
||
}
|
||
add_cards(&card_set, CardsPerRegion, cards1, ARRAY_SIZE(cards1), nullptr);
|
||
contains_cards(&card_set, CardsPerRegion, cards1, ARRAY_SIZE(cards1));
|
||
|
||
ASSERT_TRUE(card_set.num_containers() == ARRAY_SIZE(cards1));
|
||
ASSERT_TRUE(card_set.occupied() == ARRAY_SIZE(cards1));
|
||
|
||
G1CountCardsClosure count_cards;
|
||
card_set.iterate_cards(count_cards);
|
||
ASSERT_TRUE(count_cards._num_cards == ARRAY_SIZE(cards1));
|
||
|
||
check_iteration(&card_set, card_set.occupied());
|
||
|
||
card_set.clear();
|
||
ASSERT_TRUE(card_set.occupied() == 0);
|
||
}
|
||
|
||
{
|
||
G1CardSet card_set(&config, &mm);
|
||
|
||
// Generate non-prime numbers from 1 to 1000
|
||
uint count = 0;
|
||
for (uint i = 2; i < 33; i++) {
|
||
if (!card_set.contains_card(100, i)) {
|
||
for (uint j = i * i; j < 1000; j += i) {
|
||
G1AddCardResult res = card_set.add_card(100, j);
|
||
count += (res == Added);
|
||
}
|
||
}
|
||
}
|
||
|
||
G1CountCardsOccupied cl;
|
||
card_set.iterate_containers(&cl);
|
||
|
||
ASSERT_TRUE(count == card_set.occupied());
|
||
ASSERT_TRUE(card_set.occupied() == cl.num_occupied());
|
||
|
||
check_iteration(&card_set, card_set.occupied());
|
||
|
||
card_set.clear();
|
||
ASSERT_TRUE(card_set.occupied() == 0);
|
||
}
|
||
{ // Test coarsening to full
|
||
G1CardSet card_set(&config, &mm);
|
||
|
||
uint count = 0;
|
||
uint i = 10;
|
||
uint bitmap_threshold = config.cards_in_howl_bitmap_threshold();
|
||
for (; i < bitmap_threshold + 10; i++) {
|
||
G1AddCardResult res = card_set.add_card(99, i);
|
||
ASSERT_TRUE(res == Added);
|
||
count++;
|
||
ASSERT_TRUE(count == card_set.occupied());
|
||
}
|
||
|
||
G1AddCardResult res = card_set.add_card(99, config.max_cards_in_howl_bitmap() - 1);
|
||
// Adding above card should have coarsened Bitmap -> Full.
|
||
ASSERT_TRUE(res == Added);
|
||
ASSERT_TRUE(config.max_cards_in_howl_bitmap() == card_set.occupied());
|
||
|
||
res = card_set.add_card(99, config.max_cards_in_howl_bitmap() - 2);
|
||
ASSERT_TRUE(res == Found);
|
||
|
||
uint threshold = config.cards_in_howl_threshold();
|
||
uint adjusted_threshold = config.cards_in_howl_bitmap_threshold() * config.num_buckets_in_howl();
|
||
i = config.max_cards_in_howl_bitmap();
|
||
count = i;
|
||
for (; i < threshold; i++) {
|
||
G1AddCardResult res = card_set.add_card(99, i);
|
||
ASSERT_TRUE(res == Added);
|
||
count++;
|
||
ASSERT_TRUE(count == card_set.occupied());
|
||
}
|
||
|
||
res = card_set.add_card(99, CardsPerRegion - 1);
|
||
// Adding above card should have coarsened Howl -> Full.
|
||
ASSERT_TRUE(res == Added);
|
||
ASSERT_TRUE(CardsPerRegion == card_set.occupied());
|
||
|
||
check_iteration(&card_set, card_set.occupied());
|
||
|
||
res = card_set.add_card(99, CardsPerRegion - 2);
|
||
ASSERT_TRUE(res == Found);
|
||
|
||
G1CountCardsClosure count_cards;
|
||
card_set.iterate_cards(count_cards);
|
||
ASSERT_TRUE(count_cards._num_cards == config.max_cards_in_region());
|
||
|
||
card_set.clear();
|
||
ASSERT_TRUE(card_set.occupied() == 0);
|
||
}
|
||
}
|
||
|
||
class G1CardSetMtTestTask : public WorkerTask {
|
||
G1CardSet* _card_set;
|
||
|
||
size_t _added;
|
||
size_t _found;
|
||
|
||
public:
|
||
G1CardSetMtTestTask(G1CardSet* card_set) :
|
||
WorkerTask(""),
|
||
_card_set(card_set),
|
||
_added(0),
|
||
_found(0) { }
|
||
|
||
void work(uint worker_id) {
|
||
uint seed = worker_id;
|
||
size_t added = 0;
|
||
size_t found = 0;
|
||
|
||
for (uint i = 0; i < 100000; i++) {
|
||
uint region = G1CardSetTest::next_random(seed, 1000);
|
||
uint card = G1CardSetTest::next_random(seed, 10000);
|
||
|
||
G1AddCardResult res = _card_set->add_card(region, card);
|
||
|
||
ASSERT_TRUE(res == Added || res == Found);
|
||
if (res == Added) {
|
||
added++;
|
||
} else if (res == Found) {
|
||
found++;
|
||
}
|
||
}
|
||
Atomic::add(&_added, added);
|
||
Atomic::add(&_found, found);
|
||
}
|
||
|
||
size_t added() const { return _added; }
|
||
size_t found() const { return _found; }
|
||
};
|
||
|
||
void G1CardSetTest::cardset_mt_test() {
|
||
const uint CardsPerRegion = 16384;
|
||
const double FullCardSetThreshold = 1.0;
|
||
const uint BitmapCoarsenThreshold = 1.0;
|
||
|
||
G1CardSetConfiguration config(120,
|
||
BitmapCoarsenThreshold,
|
||
8,
|
||
FullCardSetThreshold,
|
||
CardsPerRegion,
|
||
0);
|
||
G1CardSetFreePool free_pool(config.num_mem_object_types());
|
||
G1CardSetMemoryManager mm(&config, &free_pool);
|
||
|
||
G1CardSet card_set(&config, &mm);
|
||
|
||
const uint num_workers = workers()->active_workers();
|
||
|
||
G1CardSetMtTestTask cl(&card_set);
|
||
|
||
{
|
||
GCTraceTime(Error, gc) x("Cardset test");
|
||
_workers->run_task(&cl, num_workers);
|
||
}
|
||
|
||
size_t num_found = 0;
|
||
// Now check the contents of the card set.
|
||
for (uint i = 0; i < num_workers; i++) {
|
||
uint seed = i;
|
||
|
||
for (uint j = 0; j < 100000; j++) {
|
||
uint region = G1CardSetTest::next_random(seed, 1000);
|
||
uint card = G1CardSetTest::next_random(seed, 10000);
|
||
|
||
bool contains = card_set.contains_card(region, card);
|
||
ASSERT_TRUE(contains);
|
||
|
||
num_found += contains;
|
||
}
|
||
}
|
||
|
||
ASSERT_TRUE(num_found == cl.added() + cl.found());
|
||
|
||
G1CountCardsClosure count_cards;
|
||
card_set.iterate_cards(count_cards);
|
||
|
||
check_iteration(&card_set, count_cards._num_cards, false /* add_was_single_threaded */);
|
||
|
||
// During coarsening we try to unblock concurrent threads as soon as possible,
|
||
// so we do not add the cards from the smaller CardSetContainer to the larger
|
||
// one immediately, allowing addition by concurrent threads after allocating
|
||
// the space immediately. So the amount of "successfully added" results may be
|
||
// (and in case of many threads typically is) higher than the number of unique
|
||
// cards.
|
||
ASSERT_TRUE(count_cards._num_cards <= cl.added());
|
||
}
|
||
|
||
TEST_VM(G1CardSetTest, basic_cardset_test) {
|
||
G1CardSetTest::cardset_basic_test();
|
||
}
|
||
|
||
TEST_VM(G1CardSetTest, mt_cardset_test) {
|
||
G1CardSetTest::cardset_mt_test();
|
||
}
|