1 // Copyright 2023 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_bluetooth_sapphire/internal/host/common/retire_log.h"
16
17 #include <gmock/gmock.h>
18 #include <gtest/gtest.h>
19
20 #include <algorithm>
21 #include <numeric>
22 #include <random>
23
24 namespace bt::internal {
25 namespace {
26
27 // Retire 101 entries where the fields in the range [starting_value,
28 // starting_value + 100]
Retire101Elements(RetireLog & retire_log,int starting_value=0)29 void Retire101Elements(RetireLog& retire_log, int starting_value = 0) {
30 std::vector<int> values(101);
31 std::iota(values.begin(), values.end(), starting_value);
32 constexpr int kSeed = 4;
33 std::shuffle(values.begin(), values.end(), std::default_random_engine(kSeed));
34 for (auto value : values) {
35 retire_log.Retire(value, std::chrono::milliseconds(value));
36 }
37 }
38
TEST(RetireLogDeathTest,InitializationLimits)39 TEST(RetireLogDeathTest, InitializationLimits) {
40 ASSERT_DEATH_IF_SUPPORTED({ RetireLog retire_log(0, 100); }, "min_depth");
41 ASSERT_DEATH_IF_SUPPORTED(
42 { RetireLog retire_log(101, 100); }, "min_depth.*max_depth");
43 ASSERT_DEATH_IF_SUPPORTED(
44 { RetireLog retire_log(1, size_t{1} << 60); }, "max_depth");
45 }
46
TEST(RetireLogDeathTest,ComputeQuantileLimits)47 TEST(RetireLogDeathTest, ComputeQuantileLimits) {
48 RetireLog retire_log(1, 100);
49 retire_log.Retire(1, std::chrono::seconds(1));
50 ASSERT_DEATH_IF_SUPPORTED(
51 {
52 [[maybe_unused]] auto _ =
53 retire_log.ComputeByteCountQuantiles(std::array{-1.});
54 },
55 "0");
56 ASSERT_DEATH_IF_SUPPORTED(
57 {
58 [[maybe_unused]] auto _ =
59 retire_log.ComputeByteCountQuantiles(std::array{2.});
60 },
61 "1");
62 }
63
TEST(RetireLogTest,QuantileCallBeforeRetiringYieldsNothing)64 TEST(RetireLogTest, QuantileCallBeforeRetiringYieldsNothing) {
65 RetireLog retire_log(1, 100);
66 EXPECT_EQ(0U, retire_log.depth());
67 auto result = retire_log.ComputeAgeQuantiles(std::array{.5});
68 EXPECT_FALSE(result.has_value());
69 }
70
TEST(RetireLogTest,QuantileCallsAfterDepthOneYieldsTheResult)71 TEST(RetireLogTest, QuantileCallsAfterDepthOneYieldsTheResult) {
72 RetireLog retire_log(1, 100);
73 constexpr pw::chrono::SystemClock::duration kTestDuration =
74 std::chrono::milliseconds(10);
75 retire_log.Retire(0, kTestDuration);
76 auto result = retire_log.ComputeAgeQuantiles(std::array{.5});
77 ASSERT_TRUE(result.has_value());
78 EXPECT_THAT(*result, testing::Each(testing::Eq(kTestDuration)));
79 }
80
TEST(RetireLogTest,ComputeQuantiles)81 TEST(RetireLogTest, ComputeQuantiles) {
82 RetireLog retire_log(1, 101);
83 Retire101Elements(retire_log);
84 auto result = retire_log.ComputeByteCountQuantiles(
85 std::array{0., .001, .5, .754, .99, 1.});
86 ASSERT_TRUE(result.has_value());
87
88 // Cutting at extremes yields the min and max entries while cutting in the
89 // middle yields the median. Cutting between entry values yields the nearest
90 // (by distribution) logged value.
91 EXPECT_THAT(*result, testing::ElementsAre(0, 0, 50, 76, 99, 100));
92 }
93
TEST(RetireLogTest,ComputeQuantilesExactBoundaryIsHighBiased)94 TEST(RetireLogTest, ComputeQuantilesExactBoundaryIsHighBiased) {
95 RetireLog retire_log(2, 2);
96 retire_log.Retire(0, {});
97 retire_log.Retire(1, {});
98 auto result = retire_log.ComputeByteCountQuantiles(std::array{.5});
99 ASSERT_TRUE(result.has_value());
100
101 // Cutting at exactly between two entries yields the higher sample
102 EXPECT_THAT(*result, testing::ElementsAre(1));
103 }
104
TEST(RetireLogTest,ComputeQuantilesOutOfOrderPartitions)105 TEST(RetireLogTest, ComputeQuantilesOutOfOrderPartitions) {
106 RetireLog retire_log(1, 101);
107 Retire101Elements(retire_log);
108 auto result = retire_log.ComputeByteCountQuantiles(std::array{.75, .25, .5});
109 ASSERT_TRUE(result.has_value());
110 EXPECT_THAT(*result, testing::ElementsAre(75, 25, 50));
111 }
112
113 // Check that cutting at the same point more than once works
TEST(RetireLogTest,ComputeSameQuantileTwice)114 TEST(RetireLogTest, ComputeSameQuantileTwice) {
115 RetireLog retire_log(1, 101);
116 Retire101Elements(retire_log);
117 auto result =
118 retire_log.ComputeByteCountQuantiles(std::array{0., 0., 1., 1.});
119 ASSERT_TRUE(result.has_value());
120 EXPECT_THAT(*result, testing::ElementsAre(0, 0, 100, 100));
121 }
122
TEST(RetireLogTest,RetiringPastMaxDepthReplacesPreviousEntries)123 TEST(RetireLogTest, RetiringPastMaxDepthReplacesPreviousEntries) {
124 RetireLog retire_log(1, 101);
125 Retire101Elements(retire_log, /*starting_value=*/0);
126 Retire101Elements(retire_log, /*starting_value=*/10);
127 EXPECT_EQ(101U, retire_log.depth());
128 auto result = retire_log.ComputeByteCountQuantiles(std::array{0., .5, 1.});
129 ASSERT_TRUE(result.has_value());
130 EXPECT_THAT(*result, testing::ElementsAre(10, 60, 110));
131 }
132
133 } // namespace
134 } // namespace bt::internal
135