backoff_entry_unittest.cc 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314
  1. // Copyright (c) 2012 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "net/base/backoff_entry.h"
  5. #include "base/time/tick_clock.h"
  6. #include "base/time/time.h"
  7. #include "testing/gtest/include/gtest/gtest.h"
  8. namespace net {
  9. namespace {
  10. using base::TimeTicks;
  11. BackoffEntry::Policy base_policy = { 0, 1000, 2.0, 0.0, 20000, 2000, false };
  12. class TestTickClock : public base::TickClock {
  13. public:
  14. TestTickClock() = default;
  15. TestTickClock(const TestTickClock&) = delete;
  16. TestTickClock& operator=(const TestTickClock&) = delete;
  17. ~TestTickClock() override = default;
  18. TimeTicks NowTicks() const override { return now_ticks_; }
  19. void set_now(TimeTicks now) { now_ticks_ = now; }
  20. private:
  21. TimeTicks now_ticks_;
  22. };
  23. TEST(BackoffEntryTest, BaseTest) {
  24. TestTickClock now_ticks;
  25. BackoffEntry entry(&base_policy, &now_ticks);
  26. EXPECT_FALSE(entry.ShouldRejectRequest());
  27. EXPECT_EQ(base::TimeDelta(), entry.GetTimeUntilRelease());
  28. entry.InformOfRequest(false);
  29. EXPECT_TRUE(entry.ShouldRejectRequest());
  30. EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
  31. }
  32. TEST(BackoffEntryTest, CanDiscardNeverExpires) {
  33. BackoffEntry::Policy never_expires_policy = base_policy;
  34. never_expires_policy.entry_lifetime_ms = -1;
  35. TestTickClock now_ticks;
  36. BackoffEntry never_expires(&never_expires_policy, &now_ticks);
  37. EXPECT_FALSE(never_expires.CanDiscard());
  38. now_ticks.set_now(TimeTicks() + base::Days(100));
  39. EXPECT_FALSE(never_expires.CanDiscard());
  40. }
  41. TEST(BackoffEntryTest, CanDiscard) {
  42. TestTickClock now_ticks;
  43. BackoffEntry entry(&base_policy, &now_ticks);
  44. // Because lifetime is non-zero, we shouldn't be able to discard yet.
  45. EXPECT_FALSE(entry.CanDiscard());
  46. // Test the "being used" case.
  47. entry.InformOfRequest(false);
  48. EXPECT_FALSE(entry.CanDiscard());
  49. // Test the case where there are errors but we can time out.
  50. now_ticks.set_now(entry.GetReleaseTime() + base::Milliseconds(1));
  51. EXPECT_FALSE(entry.CanDiscard());
  52. now_ticks.set_now(entry.GetReleaseTime() +
  53. base::Milliseconds(base_policy.maximum_backoff_ms + 1));
  54. EXPECT_TRUE(entry.CanDiscard());
  55. // Test the final case (no errors, dependent only on specified lifetime).
  56. now_ticks.set_now(entry.GetReleaseTime() +
  57. base::Milliseconds(base_policy.entry_lifetime_ms - 1));
  58. entry.InformOfRequest(true);
  59. EXPECT_FALSE(entry.CanDiscard());
  60. now_ticks.set_now(entry.GetReleaseTime() +
  61. base::Milliseconds(base_policy.entry_lifetime_ms));
  62. EXPECT_TRUE(entry.CanDiscard());
  63. }
  64. TEST(BackoffEntryTest, CanDiscardAlwaysDelay) {
  65. BackoffEntry::Policy always_delay_policy = base_policy;
  66. always_delay_policy.always_use_initial_delay = true;
  67. always_delay_policy.entry_lifetime_ms = 0;
  68. TestTickClock now_ticks;
  69. BackoffEntry entry(&always_delay_policy, &now_ticks);
  70. // Because lifetime is non-zero, we shouldn't be able to discard yet.
  71. now_ticks.set_now(entry.GetReleaseTime() + base::Milliseconds(2000));
  72. EXPECT_TRUE(entry.CanDiscard());
  73. // Even with no failures, we wait until the delay before we allow discard.
  74. entry.InformOfRequest(true);
  75. EXPECT_FALSE(entry.CanDiscard());
  76. // Wait until the delay expires, and we can discard the entry again.
  77. now_ticks.set_now(entry.GetReleaseTime() + base::Milliseconds(1000));
  78. EXPECT_TRUE(entry.CanDiscard());
  79. }
  80. TEST(BackoffEntryTest, CanDiscardNotStored) {
  81. BackoffEntry::Policy no_store_policy = base_policy;
  82. no_store_policy.entry_lifetime_ms = 0;
  83. TestTickClock now_ticks;
  84. BackoffEntry not_stored(&no_store_policy, &now_ticks);
  85. EXPECT_TRUE(not_stored.CanDiscard());
  86. }
  87. TEST(BackoffEntryTest, ShouldIgnoreFirstTwo) {
  88. BackoffEntry::Policy lenient_policy = base_policy;
  89. lenient_policy.num_errors_to_ignore = 2;
  90. BackoffEntry entry(&lenient_policy);
  91. entry.InformOfRequest(false);
  92. EXPECT_FALSE(entry.ShouldRejectRequest());
  93. entry.InformOfRequest(false);
  94. EXPECT_FALSE(entry.ShouldRejectRequest());
  95. entry.InformOfRequest(false);
  96. EXPECT_TRUE(entry.ShouldRejectRequest());
  97. }
  98. TEST(BackoffEntryTest, ReleaseTimeCalculation) {
  99. TestTickClock now_ticks;
  100. BackoffEntry entry(&base_policy, &now_ticks);
  101. // With zero errors, should return "now".
  102. TimeTicks result = entry.GetReleaseTime();
  103. EXPECT_EQ(now_ticks.NowTicks(), result);
  104. // 1 error.
  105. entry.InformOfRequest(false);
  106. result = entry.GetReleaseTime();
  107. EXPECT_EQ(now_ticks.NowTicks() + base::Milliseconds(1000), result);
  108. EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
  109. // 2 errors.
  110. entry.InformOfRequest(false);
  111. result = entry.GetReleaseTime();
  112. EXPECT_EQ(now_ticks.NowTicks() + base::Milliseconds(2000), result);
  113. EXPECT_EQ(base::Milliseconds(2000), entry.GetTimeUntilRelease());
  114. // 3 errors.
  115. entry.InformOfRequest(false);
  116. result = entry.GetReleaseTime();
  117. EXPECT_EQ(now_ticks.NowTicks() + base::Milliseconds(4000), result);
  118. EXPECT_EQ(base::Milliseconds(4000), entry.GetTimeUntilRelease());
  119. // 6 errors (to check it doesn't pass maximum).
  120. entry.InformOfRequest(false);
  121. entry.InformOfRequest(false);
  122. entry.InformOfRequest(false);
  123. result = entry.GetReleaseTime();
  124. EXPECT_EQ(now_ticks.NowTicks() + base::Milliseconds(20000), result);
  125. }
  126. TEST(BackoffEntryTest, ReleaseTimeCalculationAlwaysDelay) {
  127. BackoffEntry::Policy always_delay_policy = base_policy;
  128. always_delay_policy.always_use_initial_delay = true;
  129. always_delay_policy.num_errors_to_ignore = 2;
  130. TestTickClock now_ticks;
  131. BackoffEntry entry(&always_delay_policy, &now_ticks);
  132. // With previous requests, should return "now".
  133. TimeTicks result = entry.GetReleaseTime();
  134. EXPECT_EQ(base::TimeDelta(), entry.GetTimeUntilRelease());
  135. // 1 error.
  136. entry.InformOfRequest(false);
  137. EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
  138. // 2 errors.
  139. entry.InformOfRequest(false);
  140. EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
  141. // 3 errors, exponential backoff starts.
  142. entry.InformOfRequest(false);
  143. EXPECT_EQ(base::Milliseconds(2000), entry.GetTimeUntilRelease());
  144. // 4 errors.
  145. entry.InformOfRequest(false);
  146. EXPECT_EQ(base::Milliseconds(4000), entry.GetTimeUntilRelease());
  147. // 8 errors (to check it doesn't pass maximum).
  148. entry.InformOfRequest(false);
  149. entry.InformOfRequest(false);
  150. entry.InformOfRequest(false);
  151. entry.InformOfRequest(false);
  152. result = entry.GetReleaseTime();
  153. EXPECT_EQ(base::Milliseconds(20000), entry.GetTimeUntilRelease());
  154. }
  155. TEST(BackoffEntryTest, ReleaseTimeCalculationWithJitter) {
  156. for (int i = 0; i < 10; ++i) {
  157. BackoffEntry::Policy jittery_policy = base_policy;
  158. jittery_policy.jitter_factor = 0.2;
  159. TestTickClock now_ticks;
  160. BackoffEntry entry(&jittery_policy, &now_ticks);
  161. entry.InformOfRequest(false);
  162. entry.InformOfRequest(false);
  163. entry.InformOfRequest(false);
  164. TimeTicks result = entry.GetReleaseTime();
  165. EXPECT_LE(now_ticks.NowTicks() + base::Milliseconds(3200), result);
  166. EXPECT_GE(now_ticks.NowTicks() + base::Milliseconds(4000), result);
  167. }
  168. }
  169. TEST(BackoffEntryTest, FailureThenSuccess) {
  170. TestTickClock now_ticks;
  171. BackoffEntry entry(&base_policy, &now_ticks);
  172. // Failure count 1, establishes horizon.
  173. entry.InformOfRequest(false);
  174. TimeTicks release_time = entry.GetReleaseTime();
  175. EXPECT_EQ(TimeTicks() + base::Milliseconds(1000), release_time);
  176. // Success, failure count 0, should not advance past
  177. // the horizon that was already set.
  178. now_ticks.set_now(release_time - base::Milliseconds(200));
  179. entry.InformOfRequest(true);
  180. EXPECT_EQ(release_time, entry.GetReleaseTime());
  181. // Failure, failure count 1.
  182. entry.InformOfRequest(false);
  183. EXPECT_EQ(release_time + base::Milliseconds(800), entry.GetReleaseTime());
  184. }
  185. TEST(BackoffEntryTest, FailureThenSuccessAlwaysDelay) {
  186. BackoffEntry::Policy always_delay_policy = base_policy;
  187. always_delay_policy.always_use_initial_delay = true;
  188. always_delay_policy.num_errors_to_ignore = 1;
  189. TestTickClock now_ticks;
  190. BackoffEntry entry(&always_delay_policy, &now_ticks);
  191. // Failure count 1.
  192. entry.InformOfRequest(false);
  193. EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
  194. // Failure count 2.
  195. entry.InformOfRequest(false);
  196. EXPECT_EQ(base::Milliseconds(2000), entry.GetTimeUntilRelease());
  197. now_ticks.set_now(entry.GetReleaseTime() + base::Milliseconds(2000));
  198. // Success. We should go back to the original delay.
  199. entry.InformOfRequest(true);
  200. EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
  201. // Failure count reaches 2 again. We should increase the delay once more.
  202. entry.InformOfRequest(false);
  203. EXPECT_EQ(base::Milliseconds(2000), entry.GetTimeUntilRelease());
  204. now_ticks.set_now(entry.GetReleaseTime() + base::Milliseconds(2000));
  205. }
  206. TEST(BackoffEntryTest, RetainCustomHorizon) {
  207. TestTickClock now_ticks;
  208. BackoffEntry custom(&base_policy, &now_ticks);
  209. TimeTicks custom_horizon = TimeTicks() + base::Days(3);
  210. custom.SetCustomReleaseTime(custom_horizon);
  211. custom.InformOfRequest(false);
  212. custom.InformOfRequest(true);
  213. now_ticks.set_now(TimeTicks() + base::Days(2));
  214. custom.InformOfRequest(false);
  215. custom.InformOfRequest(true);
  216. EXPECT_EQ(custom_horizon, custom.GetReleaseTime());
  217. // Now check that once we are at or past the custom horizon,
  218. // we get normal behavior.
  219. now_ticks.set_now(TimeTicks() + base::Days(3));
  220. custom.InformOfRequest(false);
  221. EXPECT_EQ(TimeTicks() + base::Days(3) + base::Milliseconds(1000),
  222. custom.GetReleaseTime());
  223. }
  224. TEST(BackoffEntryTest, RetainCustomHorizonWhenInitialErrorsIgnored) {
  225. // Regression test for a bug discovered during code review.
  226. BackoffEntry::Policy lenient_policy = base_policy;
  227. lenient_policy.num_errors_to_ignore = 1;
  228. TestTickClock now_ticks;
  229. BackoffEntry custom(&lenient_policy, &now_ticks);
  230. TimeTicks custom_horizon = TimeTicks() + base::Days(3);
  231. custom.SetCustomReleaseTime(custom_horizon);
  232. custom.InformOfRequest(false); // This must not reset the horizon.
  233. EXPECT_EQ(custom_horizon, custom.GetReleaseTime());
  234. }
  235. TEST(BackoffEntryTest, OverflowProtection) {
  236. BackoffEntry::Policy large_multiply_policy = base_policy;
  237. large_multiply_policy.multiply_factor = 256;
  238. TestTickClock now_ticks;
  239. BackoffEntry custom(&large_multiply_policy, &now_ticks);
  240. // Trigger enough failures such that more than 11 bits of exponent are used
  241. // to represent the exponential backoff intermediate values. Given a multiply
  242. // factor of 256 (2^8), 129 iterations is enough: 2^(8*(129-1)) = 2^1024.
  243. for (int i = 0; i < 129; ++i) {
  244. now_ticks.set_now(now_ticks.NowTicks() + custom.GetTimeUntilRelease());
  245. custom.InformOfRequest(false);
  246. ASSERT_TRUE(custom.ShouldRejectRequest());
  247. }
  248. // Max delay should still be respected.
  249. EXPECT_EQ(20000, custom.GetTimeUntilRelease().InMilliseconds());
  250. }
  251. } // namespace
  252. } // namespace net