1 #include "quiche/http2/adapter/window_manager.h"
2
3 #include <list>
4
5 #include "absl/functional/bind_front.h"
6 #include "quiche/http2/test_tools/http2_random.h"
7 #include "quiche/common/platform/api/quiche_expect_bug.h"
8 #include "quiche/common/platform/api/quiche_test.h"
9
10 namespace http2 {
11 namespace adapter {
12 namespace test {
13
14 // Use the peer to access private vars of WindowManager.
15 class WindowManagerPeer {
16 public:
WindowManagerPeer(const WindowManager & wm)17 explicit WindowManagerPeer(const WindowManager& wm) : wm_(wm) {}
18
buffered()19 int64_t buffered() { return wm_.buffered_; }
20
21 private:
22 const WindowManager& wm_;
23 };
24
25 namespace {
26
27 class WindowManagerTest : public quiche::test::QuicheTest {
28 protected:
WindowManagerTest()29 WindowManagerTest()
30 : wm_(kDefaultLimit, absl::bind_front(&WindowManagerTest::OnCall, this)),
31 peer_(wm_) {}
32
OnCall(int64_t s)33 void OnCall(int64_t s) { call_sequence_.push_back(s); }
34
35 const int64_t kDefaultLimit = 32 * 1024 * 3;
36 std::list<int64_t> call_sequence_;
37 WindowManager wm_;
38 WindowManagerPeer peer_;
39 ::http2::test::Http2Random random_;
40 };
41
42 // A few no-op calls.
TEST_F(WindowManagerTest,NoOps)43 TEST_F(WindowManagerTest, NoOps) {
44 wm_.SetWindowSizeLimit(kDefaultLimit);
45 wm_.SetWindowSizeLimit(0);
46 wm_.SetWindowSizeLimit(kDefaultLimit);
47 wm_.MarkDataBuffered(0);
48 wm_.MarkDataFlushed(0);
49 EXPECT_TRUE(call_sequence_.empty());
50 }
51
52 // This test verifies that WindowManager does not notify its listener when data
53 // is only buffered, and never flushed.
TEST_F(WindowManagerTest,DataOnlyBuffered)54 TEST_F(WindowManagerTest, DataOnlyBuffered) {
55 int64_t total = 0;
56 while (total < kDefaultLimit) {
57 int64_t s = std::min<int64_t>(kDefaultLimit - total, random_.Uniform(1024));
58 total += s;
59 wm_.MarkDataBuffered(s);
60 }
61 EXPECT_THAT(call_sequence_, ::testing::IsEmpty());
62 }
63
64 // This test verifies that WindowManager does notify its listener when data is
65 // buffered and subsequently flushed.
TEST_F(WindowManagerTest,DataBufferedAndFlushed)66 TEST_F(WindowManagerTest, DataBufferedAndFlushed) {
67 int64_t total_buffered = 0;
68 int64_t total_flushed = 0;
69 while (call_sequence_.empty()) {
70 int64_t buffered = std::min<int64_t>(kDefaultLimit - total_buffered,
71 random_.Uniform(1024));
72 wm_.MarkDataBuffered(buffered);
73 total_buffered += buffered;
74 EXPECT_TRUE(call_sequence_.empty());
75 int64_t flushed = (total_buffered - total_flushed) > 0
76 ? random_.Uniform(total_buffered - total_flushed)
77 : 0;
78 wm_.MarkDataFlushed(flushed);
79 total_flushed += flushed;
80 }
81 // If WindowManager decided to send an update, at least one third of the
82 // window must have been consumed by buffered data.
83 EXPECT_GE(total_buffered, kDefaultLimit / 3);
84 }
85
86 // Window manager should avoid window underflow.
TEST_F(WindowManagerTest,AvoidWindowUnderflow)87 TEST_F(WindowManagerTest, AvoidWindowUnderflow) {
88 EXPECT_EQ(wm_.CurrentWindowSize(), wm_.WindowSizeLimit());
89 // Don't buffer more than the total window!
90 wm_.MarkDataBuffered(wm_.WindowSizeLimit() + 1);
91 EXPECT_EQ(wm_.CurrentWindowSize(), 0u);
92 }
93
94 // Window manager should GFE_BUG and avoid buffered underflow.
TEST_F(WindowManagerTest,AvoidBufferedUnderflow)95 TEST_F(WindowManagerTest, AvoidBufferedUnderflow) {
96 EXPECT_EQ(peer_.buffered(), 0u);
97 // Don't flush more than has been buffered!
98 EXPECT_QUICHE_BUG(wm_.MarkDataFlushed(1), "buffered underflow");
99 EXPECT_EQ(peer_.buffered(), 0u);
100
101 wm_.MarkDataBuffered(42);
102 EXPECT_EQ(peer_.buffered(), 42u);
103 // Don't flush more than has been buffered!
104 EXPECT_QUICHE_BUG(
105 {
106 wm_.MarkDataFlushed(43);
107 EXPECT_EQ(peer_.buffered(), 0u);
108 },
109 "buffered underflow");
110 }
111
112 // This test verifies that WindowManager notifies its listener when window is
113 // consumed (data is ignored or immediately dropped).
TEST_F(WindowManagerTest,WindowConsumed)114 TEST_F(WindowManagerTest, WindowConsumed) {
115 int64_t consumed = kDefaultLimit / 3 - 1;
116 wm_.MarkWindowConsumed(consumed);
117 EXPECT_TRUE(call_sequence_.empty());
118 const int64_t extra = 1;
119 wm_.MarkWindowConsumed(extra);
120 EXPECT_THAT(call_sequence_, testing::ElementsAre(consumed + extra));
121 }
122
123 // This test verifies that WindowManager notifies its listener when the window
124 // size limit is increased.
TEST_F(WindowManagerTest,ListenerCalledOnSizeUpdate)125 TEST_F(WindowManagerTest, ListenerCalledOnSizeUpdate) {
126 wm_.SetWindowSizeLimit(kDefaultLimit - 1024);
127 EXPECT_TRUE(call_sequence_.empty());
128 wm_.SetWindowSizeLimit(kDefaultLimit * 5);
129 // Because max(outstanding window, previous limit) is kDefaultLimit, it is
130 // only appropriate to increase the window by kDefaultLimit * 4.
131 EXPECT_THAT(call_sequence_, testing::ElementsAre(kDefaultLimit * 4));
132 }
133
134 // This test verifies that when data is buffered and then the limit is
135 // decreased, WindowManager only notifies the listener once any outstanding
136 // window has been consumed.
TEST_F(WindowManagerTest,WindowUpdateAfterLimitDecreased)137 TEST_F(WindowManagerTest, WindowUpdateAfterLimitDecreased) {
138 wm_.MarkDataBuffered(kDefaultLimit - 1024);
139 wm_.SetWindowSizeLimit(kDefaultLimit - 2048);
140
141 // Now there are 2048 bytes of window outstanding beyond the current limit,
142 // and we have 1024 bytes of data buffered beyond the current limit. This is
143 // intentional, to be sure that WindowManager works properly if the limit is
144 // decreased at runtime.
145
146 wm_.MarkDataFlushed(512);
147 EXPECT_TRUE(call_sequence_.empty());
148 wm_.MarkDataFlushed(512);
149 EXPECT_TRUE(call_sequence_.empty());
150 wm_.MarkDataFlushed(512);
151 EXPECT_TRUE(call_sequence_.empty());
152 wm_.MarkDataFlushed(1024);
153 EXPECT_THAT(call_sequence_, testing::ElementsAre(512));
154 }
155
156 // For normal behavior, we only call MaybeNotifyListener() when data is
157 // flushed. But if window runs out entirely, we still need to call
158 // MaybeNotifyListener() to avoid becoming artificially blocked when data isn't
159 // being flushed.
TEST_F(WindowManagerTest,ZeroWindowNotification)160 TEST_F(WindowManagerTest, ZeroWindowNotification) {
161 // Consume a byte of window, but not enough to trigger an update.
162 wm_.MarkWindowConsumed(1);
163
164 // Buffer the remaining window.
165 wm_.MarkDataBuffered(kDefaultLimit - 1);
166 // Listener is notified of the remaining byte of possible window.
167 EXPECT_THAT(call_sequence_, testing::ElementsAre(1));
168 }
169
TEST_F(WindowManagerTest,OnWindowSizeLimitChange)170 TEST_F(WindowManagerTest, OnWindowSizeLimitChange) {
171 wm_.MarkDataBuffered(10000);
172 EXPECT_EQ(wm_.CurrentWindowSize(), kDefaultLimit - 10000);
173 EXPECT_EQ(wm_.WindowSizeLimit(), kDefaultLimit);
174
175 wm_.OnWindowSizeLimitChange(kDefaultLimit + 1000);
176 EXPECT_EQ(wm_.CurrentWindowSize(), kDefaultLimit - 9000);
177 EXPECT_EQ(wm_.WindowSizeLimit(), kDefaultLimit + 1000);
178
179 wm_.OnWindowSizeLimitChange(kDefaultLimit - 1000);
180 EXPECT_EQ(wm_.CurrentWindowSize(), kDefaultLimit - 11000);
181 EXPECT_EQ(wm_.WindowSizeLimit(), kDefaultLimit - 1000);
182 }
183
TEST_F(WindowManagerTest,NegativeWindowSize)184 TEST_F(WindowManagerTest, NegativeWindowSize) {
185 wm_.MarkDataBuffered(80000);
186 // 98304 window - 80000 buffered = 18304 available
187 EXPECT_EQ(wm_.CurrentWindowSize(), 18304);
188 wm_.OnWindowSizeLimitChange(65535);
189 // limit decreases by 98304 - 65535 = 32769, window becomes -14465
190 EXPECT_EQ(wm_.CurrentWindowSize(), -14465);
191 wm_.MarkDataFlushed(70000);
192 // Still 10000 bytes buffered, so window manager grants sufficient quota to
193 // reach a window of 65535 - 10000.
194 EXPECT_EQ(wm_.CurrentWindowSize(), 55535);
195 // Desired window minus existing window: 55535 - (-14465) = 70000
196 EXPECT_THAT(call_sequence_, testing::ElementsAre(70000));
197 }
198
TEST_F(WindowManagerTest,IncreaseWindow)199 TEST_F(WindowManagerTest, IncreaseWindow) {
200 wm_.MarkDataBuffered(1000);
201 EXPECT_EQ(wm_.CurrentWindowSize(), kDefaultLimit - 1000);
202 EXPECT_EQ(wm_.WindowSizeLimit(), kDefaultLimit);
203
204 // Increasing the window beyond the limit is allowed.
205 wm_.IncreaseWindow(5000);
206 EXPECT_EQ(wm_.CurrentWindowSize(), kDefaultLimit + 4000);
207 EXPECT_EQ(wm_.WindowSizeLimit(), kDefaultLimit);
208
209 // 80000 bytes are buffered, then flushed.
210 wm_.MarkWindowConsumed(80000);
211 // The window manager replenishes the consumed quota up to the limit.
212 EXPECT_THAT(call_sequence_, testing::ElementsAre(75000));
213 // The window is the limit, minus buffered data, as expected.
214 EXPECT_EQ(wm_.CurrentWindowSize(), kDefaultLimit - 1000);
215 }
216
217 // This test verifies that when the constructor option is specified,
218 // WindowManager does not update its internal accounting of the flow control
219 // window when notifying the listener.
TEST(WindowManagerNoUpdateTest,NoWindowUpdateOnListener)220 TEST(WindowManagerNoUpdateTest, NoWindowUpdateOnListener) {
221 const int64_t kDefaultLimit = 65535;
222
223 std::list<int64_t> call_sequence1;
224 WindowManager wm1(
225 kDefaultLimit,
226 [&call_sequence1](int64_t delta) { call_sequence1.push_back(delta); },
227 /*should_notify_listener=*/{},
228 /*update_window_on_notify=*/true); // default
229 std::list<int64_t> call_sequence2;
230 WindowManager wm2(
231 kDefaultLimit,
232 [&call_sequence2](int64_t delta) { call_sequence2.push_back(delta); },
233 /*should_notify_listener=*/{},
234 /*update_window_on_notify=*/false);
235
236 const int64_t consumed = kDefaultLimit / 3 - 1;
237
238 wm1.MarkWindowConsumed(consumed);
239 EXPECT_TRUE(call_sequence1.empty());
240 wm2.MarkWindowConsumed(consumed);
241 EXPECT_TRUE(call_sequence2.empty());
242
243 EXPECT_EQ(wm1.CurrentWindowSize(), kDefaultLimit - consumed);
244 EXPECT_EQ(wm2.CurrentWindowSize(), kDefaultLimit - consumed);
245
246 const int64_t extra = 1;
247 wm1.MarkWindowConsumed(extra);
248 EXPECT_THAT(call_sequence1, testing::ElementsAre(consumed + extra));
249 // Window size *is* updated after invoking the listener.
250 EXPECT_EQ(wm1.CurrentWindowSize(), kDefaultLimit);
251 call_sequence1.clear();
252
253 wm2.MarkWindowConsumed(extra);
254 EXPECT_THAT(call_sequence2, testing::ElementsAre(consumed + extra));
255 // Window size is *not* updated after invoking the listener.
256 EXPECT_EQ(wm2.CurrentWindowSize(), kDefaultLimit - (consumed + extra));
257 call_sequence2.clear();
258
259 // Manually increase the window by the listener notification amount.
260 wm2.IncreaseWindow(consumed + extra);
261 EXPECT_EQ(wm2.CurrentWindowSize(), kDefaultLimit);
262
263 wm1.SetWindowSizeLimit(kDefaultLimit * 5);
264 EXPECT_THAT(call_sequence1, testing::ElementsAre(kDefaultLimit * 4));
265 // *Does* update the window size.
266 EXPECT_EQ(wm1.CurrentWindowSize(), kDefaultLimit * 5);
267
268 wm2.SetWindowSizeLimit(kDefaultLimit * 5);
269 EXPECT_THAT(call_sequence2, testing::ElementsAre(kDefaultLimit * 4));
270 // Does *not* update the window size.
271 EXPECT_EQ(wm2.CurrentWindowSize(), kDefaultLimit);
272 }
273
274 // This test verifies that when the constructor option is specified,
275 // WindowManager uses the provided ShouldWindowUpdateFn to determine when to
276 // notify the listener.
TEST(WindowManagerShouldUpdateTest,CustomShouldWindowUpdateFn)277 TEST(WindowManagerShouldUpdateTest, CustomShouldWindowUpdateFn) {
278 const int64_t kDefaultLimit = 65535;
279
280 // This window manager should always notify.
281 std::list<int64_t> call_sequence1;
282 WindowManager wm1(
283 kDefaultLimit,
284 [&call_sequence1](int64_t delta) { call_sequence1.push_back(delta); },
285 [](int64_t /*limit*/, int64_t /*window*/, int64_t /*delta*/) {
286 return true;
287 });
288 // This window manager should never notify.
289 std::list<int64_t> call_sequence2;
290 WindowManager wm2(
291 kDefaultLimit,
292 [&call_sequence2](int64_t delta) { call_sequence2.push_back(delta); },
293 [](int64_t /*limit*/, int64_t /*window*/, int64_t /*delta*/) {
294 return false;
295 });
296 // This window manager should notify as long as no data is buffered.
297 std::list<int64_t> call_sequence3;
298 WindowManager wm3(
299 kDefaultLimit,
300 [&call_sequence3](int64_t delta) { call_sequence3.push_back(delta); },
301 [](int64_t limit, int64_t window, int64_t delta) {
302 return delta == limit - window;
303 });
304
305 const int64_t consumed = kDefaultLimit / 4;
306
307 wm1.MarkWindowConsumed(consumed);
308 EXPECT_THAT(call_sequence1, testing::ElementsAre(consumed));
309 wm2.MarkWindowConsumed(consumed);
310 EXPECT_TRUE(call_sequence2.empty());
311 wm3.MarkWindowConsumed(consumed);
312 EXPECT_THAT(call_sequence3, testing::ElementsAre(consumed));
313
314 const int64_t buffered = 42;
315
316 wm1.MarkDataBuffered(buffered);
317 EXPECT_THAT(call_sequence1, testing::ElementsAre(consumed));
318 wm2.MarkDataBuffered(buffered);
319 EXPECT_TRUE(call_sequence2.empty());
320 wm3.MarkDataBuffered(buffered);
321 EXPECT_THAT(call_sequence3, testing::ElementsAre(consumed));
322
323 wm1.MarkDataFlushed(buffered / 3);
324 EXPECT_THAT(call_sequence1, testing::ElementsAre(consumed, buffered / 3));
325 wm2.MarkDataFlushed(buffered / 3);
326 EXPECT_TRUE(call_sequence2.empty());
327 wm3.MarkDataFlushed(buffered / 3);
328 EXPECT_THAT(call_sequence3, testing::ElementsAre(consumed));
329
330 wm1.MarkDataFlushed(2 * buffered / 3);
331 EXPECT_THAT(call_sequence1,
332 testing::ElementsAre(consumed, buffered / 3, 2 * buffered / 3));
333 wm2.MarkDataFlushed(2 * buffered / 3);
334 EXPECT_TRUE(call_sequence2.empty());
335 wm3.MarkDataFlushed(2 * buffered / 3);
336 EXPECT_THAT(call_sequence3, testing::ElementsAre(consumed, buffered));
337 }
338
339 } // namespace
340 } // namespace test
341 } // namespace adapter
342 } // namespace http2
343