From d027d285cc0442bccba5cc15aca668d2411f37c2 Mon Sep 17 00:00:00 2001 From: Adam Kupczyk Date: Wed, 22 Feb 2023 18:24:41 +0100 Subject: [PATCH] os/Allocator_tests: Add dedicated test for fragmentation score Add special tests for fragmentation score. Give broad range, but require them to follow certain behavours. Signed-off-by: Adam Kupczyk (cherry picked from commit 5b54a13354fbea5d59e8d9ab6015eff7d6d05954) --- src/test/objectstore/Allocator_test.cc | 83 ++++++++++++++++++++++++-- 1 file changed, 77 insertions(+), 6 deletions(-) diff --git a/src/test/objectstore/Allocator_test.cc b/src/test/objectstore/Allocator_test.cc index b006500153c6e..186063aa7f799 100644 --- a/src/test/objectstore/Allocator_test.cc +++ b/src/test/objectstore/Allocator_test.cc @@ -301,7 +301,6 @@ TEST_P(AllocTest, test_alloc_fragmentation) alloc->release(release_set); } EXPECT_EQ(1.0, alloc->get_fragmentation()); - EXPECT_EQ(66u, uint64_t(alloc->get_fragmentation_score() * 100)); for (size_t i = 1; i < allocated.size() / 2; i += 2) { @@ -316,7 +315,6 @@ TEST_P(AllocTest, test_alloc_fragmentation) // fragmentation approx = 257 intervals / 768 max intervals EXPECT_EQ(33u, uint64_t(alloc->get_fragmentation() * 100)); } - EXPECT_EQ(27u, uint64_t(alloc->get_fragmentation_score() * 100)); for (size_t i = allocated.size() / 2 + 1; i < allocated.size(); i += 2) { @@ -329,11 +327,84 @@ TEST_P(AllocTest, test_alloc_fragmentation) // Hence leaving just two // digits after decimal point due to this. EXPECT_EQ(0u, uint64_t(alloc->get_fragmentation() * 100)); - if (bitmap_alloc) { - EXPECT_EQ(0u, uint64_t(alloc->get_fragmentation_score() * 100)); - } else { - EXPECT_EQ(11u, uint64_t(alloc->get_fragmentation_score() * 100)); +} + +TEST_P(AllocTest, test_fragmentation_score_0) +{ + uint64_t capacity = 16LL * 1024 * 1024 * 1024; //16 GB, very small + uint64_t alloc_unit = 4096; + + init_alloc(capacity, alloc_unit); + alloc->init_add_free(0, capacity); + EXPECT_EQ(0, alloc->get_fragmentation_score()); + + // alloc every 100M, should get very small score + for (uint64_t pos = 0; pos < capacity; pos += 100 * 1024 * 1024) { + alloc->init_rm_free(pos, alloc_unit); + } + EXPECT_LT(alloc->get_fragmentation_score(), 0.0001); // frag < 0.01% + for (uint64_t pos = 0; pos < capacity; pos += 100 * 1024 * 1024) { + // put back + alloc->init_add_free(pos, alloc_unit); + } + + // 10% space is trashed, rest is free, small score + for (uint64_t pos = 0; pos < capacity / 10; pos += 3 * alloc_unit) { + alloc->init_rm_free(pos, alloc_unit); + } + EXPECT_LT(0.01, alloc->get_fragmentation_score()); // 1% < frag < 10% + EXPECT_LT(alloc->get_fragmentation_score(), 0.1); +} + +TEST_P(AllocTest, test_fragmentation_score_some) +{ + uint64_t capacity = 1024 * 1024 * 1024; //1 GB, very small + uint64_t alloc_unit = 4096; + + init_alloc(capacity, alloc_unit); + alloc->init_add_free(0, capacity); + // half (in 16 chunks) is completely free, + // other half completely fragmented, expect less than 50% fragmentation score + for (uint64_t chunk = 0; chunk < capacity; chunk += capacity / 16) { + for (uint64_t pos = 0; pos < capacity / 32; pos += alloc_unit * 3) { + alloc->init_rm_free(chunk + pos, alloc_unit); + } + } + EXPECT_LT(alloc->get_fragmentation_score(), 0.5); // f < 50% + + init_alloc(capacity, alloc_unit); + alloc->init_add_free(0, capacity); + // half (in 16 chunks) is completely full, + // other half completely fragmented, expect really high fragmentation score + for (uint64_t chunk = 0; chunk < capacity; chunk += capacity / 16) { + alloc->init_rm_free(chunk + capacity / 32, capacity / 32); + for (uint64_t pos = 0; pos < capacity / 32; pos += alloc_unit * 3) { + alloc->init_rm_free(chunk + pos, alloc_unit); + } + } + EXPECT_LT(0.9, alloc->get_fragmentation_score()); // 50% < f +} + +TEST_P(AllocTest, test_fragmentation_score_1) +{ + uint64_t capacity = 1024 * 1024 * 1024; //1 GB, very small + uint64_t alloc_unit = 4096; + + init_alloc(capacity, alloc_unit); + alloc->init_add_free(0, capacity); + // alloc every second AU, max fragmentation + for (uint64_t pos = 0; pos < capacity; pos += alloc_unit * 2) { + alloc->init_rm_free(pos, alloc_unit); + } + EXPECT_LT(0.99, alloc->get_fragmentation_score()); // 99% < f + + init_alloc(capacity, alloc_unit); + alloc->init_add_free(0, capacity); + // 1 allocated, 4 empty; expect very high score + for (uint64_t pos = 0; pos < capacity; pos += alloc_unit * 5) { + alloc->init_rm_free(pos, alloc_unit); } + EXPECT_LT(0.90, alloc->get_fragmentation_score()); // 90% < f } TEST_P(AllocTest, test_dump_fragmentation_score) -- 2.39.5