1 // Copyright 2023 gRPC authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://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,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "src/core/lib/backoff/random_early_detection.h"
16
17 #include <memory>
18
19 #include "absl/random/random.h"
20 #include "gtest/gtest.h"
21
22 namespace grpc_core {
23 namespace {
24
TEST(RandomEarlyDetectionTest,NoOp)25 TEST(RandomEarlyDetectionTest, NoOp) {
26 RandomEarlyDetection red(100, 200);
27 EXPECT_EQ(red.soft_limit(), 100);
28 EXPECT_EQ(red.hard_limit(), 200);
29 }
30
TEST(RandomEarlyDetectionTest,Distribution)31 TEST(RandomEarlyDetectionTest, Distribution) {
32 absl::BitGen bitgen;
33 RandomEarlyDetection red(100, 200);
34 int64_t counts[300] = {};
35 for (int round = 0; round < 10000; round++) {
36 for (int64_t i = 0; i < 300; i++) {
37 if (red.Reject(i, absl::BitGenRef(bitgen))) counts[i]++;
38 }
39 }
40 for (int64_t i = 0; i < 100; i++) {
41 // [0, 100) should never be rejected
42 EXPECT_EQ(counts[i], 0) << i;
43 // [100, 200) should be rejected with probability ramping from 0 to 1
44 EXPECT_GT(counts[i + 100], (i - 5) * 100) << i;
45 EXPECT_LT(counts[i + 100], (i + 5) * 100) << i;
46 // [200, 300) should always be rejected
47 EXPECT_EQ(counts[i + 200], 10000) << i;
48 }
49 }
50
TEST(RandomEarlyDetection,MustRejectWorks)51 TEST(RandomEarlyDetection, MustRejectWorks) {
52 RandomEarlyDetection red(100, 200);
53 for (int64_t i = 0; i < 200; i++) {
54 EXPECT_FALSE(red.MustReject(i));
55 }
56 for (int64_t i = 200; i < 300; i++) {
57 EXPECT_TRUE(red.MustReject(i));
58 }
59 }
60
61 } // namespace
62 } // namespace grpc_core
63
main(int argc,char ** argv)64 int main(int argc, char** argv) {
65 ::testing::InitGoogleTest(&argc, argv);
66 return RUN_ALL_TESTS();
67 }
68