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 }
44
TEST(RetireLogDeathTest,ComputeQuantileLimits)45 TEST(RetireLogDeathTest, ComputeQuantileLimits) {
46 RetireLog retire_log(1, 100);
47 retire_log.Retire(1, std::chrono::seconds(1));
48 ASSERT_DEATH_IF_SUPPORTED(
49 {
50 [[maybe_unused]] auto _ =
51 retire_log.ComputeByteCountQuantiles(std::array{-1.});
52 },
53 "0");
54 ASSERT_DEATH_IF_SUPPORTED(
55 {
56 [[maybe_unused]] auto _ =
57 retire_log.ComputeByteCountQuantiles(std::array{2.});
58 },
59 "1");
60 }
61
TEST(RetireLogTest,QuantileCallBeforeRetiringYieldsNothing)62 TEST(RetireLogTest, QuantileCallBeforeRetiringYieldsNothing) {
63 RetireLog retire_log(1, 100);
64 EXPECT_EQ(0U, retire_log.depth());
65 auto result = retire_log.ComputeAgeQuantiles(std::array{.5});
66 EXPECT_FALSE(result.has_value());
67 }
68
TEST(RetireLogTest,QuantileCallsAfterDepthOneYieldsTheResult)69 TEST(RetireLogTest, QuantileCallsAfterDepthOneYieldsTheResult) {
70 RetireLog retire_log(1, 100);
71 constexpr pw::chrono::SystemClock::duration kTestDuration =
72 std::chrono::milliseconds(10);
73 retire_log.Retire(0, kTestDuration);
74 auto result = retire_log.ComputeAgeQuantiles(std::array{.5});
75 ASSERT_TRUE(result.has_value());
76 EXPECT_THAT(*result, testing::Each(testing::Eq(kTestDuration)));
77 }
78
TEST(RetireLogTest,ComputeQuantiles)79 TEST(RetireLogTest, ComputeQuantiles) {
80 RetireLog retire_log(1, 101);
81 Retire101Elements(retire_log);
82 auto result = retire_log.ComputeByteCountQuantiles(
83 std::array{0., .001, .5, .754, .99, 1.});
84 ASSERT_TRUE(result.has_value());
85
86 // Cutting at extremes yields the min and max entries while cutting in the
87 // middle yields the median. Cutting between entry values yields the nearest
88 // (by distribution) logged value.
89 EXPECT_THAT(*result, testing::ElementsAre(0, 0, 50, 76, 99, 100));
90 }
91
TEST(RetireLogTest,ComputeQuantilesExactBoundaryIsHighBiased)92 TEST(RetireLogTest, ComputeQuantilesExactBoundaryIsHighBiased) {
93 RetireLog retire_log(2, 2);
94 retire_log.Retire(0, {});
95 retire_log.Retire(1, {});
96 auto result = retire_log.ComputeByteCountQuantiles(std::array{.5});
97 ASSERT_TRUE(result.has_value());
98
99 // Cutting at exactly between two entries yields the higher sample
100 EXPECT_THAT(*result, testing::ElementsAre(1));
101 }
102
TEST(RetireLogTest,ComputeQuantilesOutOfOrderPartitions)103 TEST(RetireLogTest, ComputeQuantilesOutOfOrderPartitions) {
104 RetireLog retire_log(1, 101);
105 Retire101Elements(retire_log);
106 auto result = retire_log.ComputeByteCountQuantiles(std::array{.75, .25, .5});
107 ASSERT_TRUE(result.has_value());
108 EXPECT_THAT(*result, testing::ElementsAre(75, 25, 50));
109 }
110
111 // Check that cutting at the same point more than once works
TEST(RetireLogTest,ComputeSameQuantileTwice)112 TEST(RetireLogTest, ComputeSameQuantileTwice) {
113 RetireLog retire_log(1, 101);
114 Retire101Elements(retire_log);
115 auto result =
116 retire_log.ComputeByteCountQuantiles(std::array{0., 0., 1., 1.});
117 ASSERT_TRUE(result.has_value());
118 EXPECT_THAT(*result, testing::ElementsAre(0, 0, 100, 100));
119 }
120
TEST(RetireLogTest,RetiringPastMaxDepthReplacesPreviousEntries)121 TEST(RetireLogTest, RetiringPastMaxDepthReplacesPreviousEntries) {
122 RetireLog retire_log(1, 101);
123 Retire101Elements(retire_log, /*starting_value=*/0);
124 Retire101Elements(retire_log, /*starting_value=*/10);
125 EXPECT_EQ(101U, retire_log.depth());
126 auto result = retire_log.ComputeByteCountQuantiles(std::array{0., .5, 1.});
127 ASSERT_TRUE(result.has_value());
128 EXPECT_THAT(*result, testing::ElementsAre(10, 60, 110));
129 }
130
131 } // namespace
132 } // namespace bt::internal
133