| // Copyright 2021 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "retire_log.h" |
| |
| #include <algorithm> |
| #include <numeric> |
| #include <random> |
| |
| #include <gmock/gmock.h> |
| #include <gtest/gtest.h> |
| |
| #include "lib/zx/time.h" |
| |
| namespace bt::internal { |
| namespace { |
| |
| // Retire 101 entries where the fields in the range [starting_value, starting_value + 100] |
| void Retire101Elements(RetireLog& retire_log, int starting_value = 0) { |
| std::vector<int> values(101); |
| std::iota(values.begin(), values.end(), starting_value); |
| constexpr int kSeed = 4; |
| std::shuffle(values.begin(), values.end(), std::default_random_engine(kSeed)); |
| for (auto value : values) { |
| retire_log.Retire(value, zx::msec(value)); |
| } |
| } |
| |
| TEST(RetireLogDeathTest, InitializationLimits) { |
| ASSERT_DEATH_IF_SUPPORTED({ RetireLog retire_log(0, 100); }, "min_depth"); |
| ASSERT_DEATH_IF_SUPPORTED({ RetireLog retire_log(101, 100); }, "min_depth.*max_depth"); |
| ASSERT_DEATH_IF_SUPPORTED({ RetireLog retire_log(1, size_t{1} << 60); }, "max_depth"); |
| } |
| |
| TEST(RetireLogDeathTest, ComputeQuantileLimits) { |
| RetireLog retire_log(1, 100); |
| retire_log.Retire(1, zx::sec(1)); |
| ASSERT_DEATH_IF_SUPPORTED( |
| { [[maybe_unused]] auto _ = retire_log.ComputeByteCountQuantiles(std::array{-1.}); }, "0"); |
| ASSERT_DEATH_IF_SUPPORTED( |
| { [[maybe_unused]] auto _ = retire_log.ComputeByteCountQuantiles(std::array{2.}); }, "1"); |
| } |
| |
| TEST(RetireLogTest, QuantileCallBeforeRetiringYieldsNothing) { |
| RetireLog retire_log(1, 100); |
| EXPECT_EQ(0U, retire_log.depth()); |
| auto result = retire_log.ComputeAgeQuantiles(std::array{.5}); |
| EXPECT_FALSE(result.has_value()); |
| } |
| |
| TEST(RetireLogTest, QuantileCallsAfterDepthOneYieldsTheResult) { |
| RetireLog retire_log(1, 100); |
| constexpr zx::duration kTestDuration = zx::msec(10); |
| retire_log.Retire(0, kTestDuration); |
| auto result = retire_log.ComputeAgeQuantiles(std::array{.5}); |
| ASSERT_TRUE(result.has_value()); |
| EXPECT_THAT(*result, testing::Each(testing::Eq(kTestDuration))); |
| } |
| |
| TEST(RetireLogTest, ComputeQuantiles) { |
| RetireLog retire_log(1, 101); |
| Retire101Elements(retire_log); |
| auto result = retire_log.ComputeByteCountQuantiles(std::array{0., .001, .5, .754, .99, 1.}); |
| ASSERT_TRUE(result.has_value()); |
| |
| // Cutting at extremes yields the min and max entries while cutting in the middle yields the |
| // median. Cutting between entry values yields the nearest (by distribution) logged value. |
| EXPECT_THAT(*result, testing::ElementsAre(0, 0, 50, 76, 99, 100)); |
| } |
| |
| TEST(RetireLogTest, ComputeQuantilesExactBoundaryIsHighBiased) { |
| RetireLog retire_log(2, 2); |
| retire_log.Retire(0, {}); |
| retire_log.Retire(1, {}); |
| auto result = retire_log.ComputeByteCountQuantiles(std::array{.5}); |
| ASSERT_TRUE(result.has_value()); |
| |
| // Cutting at exactly between two entries yields the higher sample |
| EXPECT_THAT(*result, testing::ElementsAre(1)); |
| } |
| |
| TEST(RetireLogTest, ComputeQuantilesOutOfOrderPartitions) { |
| RetireLog retire_log(1, 101); |
| Retire101Elements(retire_log); |
| auto result = retire_log.ComputeByteCountQuantiles(std::array{.75, .25, .5}); |
| ASSERT_TRUE(result.has_value()); |
| EXPECT_THAT(*result, testing::ElementsAre(75, 25, 50)); |
| } |
| |
| // Check that cutting at the same point more than once works |
| TEST(RetireLogTest, ComputeSameQuantileTwice) { |
| RetireLog retire_log(1, 101); |
| Retire101Elements(retire_log); |
| auto result = retire_log.ComputeByteCountQuantiles(std::array{0., 0., 1., 1.}); |
| ASSERT_TRUE(result.has_value()); |
| EXPECT_THAT(*result, testing::ElementsAre(0, 0, 100, 100)); |
| } |
| |
| TEST(RetireLogTest, RetiringPastMaxDepthReplacesPreviousEntries) { |
| RetireLog retire_log(1, 101); |
| Retire101Elements(retire_log, /*starting_value=*/0); |
| Retire101Elements(retire_log, /*starting_value=*/10); |
| EXPECT_EQ(101U, retire_log.depth()); |
| auto result = retire_log.ComputeByteCountQuantiles(std::array{0., .5, 1.}); |
| ASSERT_TRUE(result.has_value()); |
| EXPECT_THAT(*result, testing::ElementsAre(10, 60, 110)); |
| } |
| |
| } // namespace |
| } // namespace bt::internal |