1 // Copyright 2016 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
5 #include "net/spdy/http2_priority_dependencies.h"
6
7 #include <algorithm>
8
9 #include "testing/gmock/include/gmock/gmock.h"
10 #include "testing/platform_test.h"
11
12 using ::testing::ContainerEq;
13
14 namespace net {
15
operator ==(const Http2PriorityDependencies::DependencyUpdate & a,const Http2PriorityDependencies::DependencyUpdate & b)16 bool operator==(const Http2PriorityDependencies::DependencyUpdate& a,
17 const Http2PriorityDependencies::DependencyUpdate& b) {
18 return a.id == b.id && a.parent_stream_id == b.parent_stream_id &&
19 a.weight == b.weight && a.exclusive == b.exclusive;
20 }
21
operator <<(std::ostream & os,const std::vector<Http2PriorityDependencies::DependencyUpdate> & v)22 std::ostream& operator<<(
23 std::ostream& os,
24 const std::vector<Http2PriorityDependencies::DependencyUpdate>& v) {
25 for (auto e : v) {
26 os << "{" << e.id << "," << e.parent_stream_id << "," << e.weight << ","
27 << (e.exclusive ? "true" : "false") << "}";
28 }
29 return os;
30 }
31
32 class HttpPriorityDependencyTest : public PlatformTest {
33 public:
HttpPriorityDependencyTest()34 HttpPriorityDependencyTest() : next_id_(0u) {}
35
36 // Fixed priority values to use for testing.
37 enum {
38 HIGHEST = spdy::kV3HighestPriority,
39 MEDIUM = HIGHEST + 1,
40 LOW = MEDIUM + 1,
41 LOWEST = spdy::kV3LowestPriority,
42 };
43
GetId()44 spdy::SpdyStreamId GetId() { return ++next_id_; }
45
TestStreamCreation(spdy::SpdyStreamId new_id,spdy::SpdyPriority priority,spdy::SpdyStreamId expected_parent_id)46 void TestStreamCreation(spdy::SpdyStreamId new_id,
47 spdy::SpdyPriority priority,
48 spdy::SpdyStreamId expected_parent_id) {
49 int expected_weight = spdy::Spdy3PriorityToHttp2Weight(priority);
50
51 spdy::SpdyStreamId parent_id = 999u;
52 int weight = -1;
53 bool exclusive = false;
54 dependency_state_.OnStreamCreation(new_id, priority, &parent_id, &weight,
55 &exclusive);
56 if (expected_parent_id != parent_id || !exclusive ||
57 expected_weight != weight) {
58 ADD_FAILURE() << "OnStreamCreation(" << new_id << ", " << int(priority)
59 << ")\n"
60 << " Got: (" << parent_id << ", " << weight << ", "
61 << exclusive << ")\n"
62 << " Want: (" << expected_parent_id << ", "
63 << expected_weight << ", true)\n";
64 }
65 }
66
67 struct ExpectedDependencyUpdate {
68 spdy::SpdyStreamId id;
69 spdy::SpdyStreamId parent_id;
70 int weight;
71 };
72
TestStreamUpdate(spdy::SpdyStreamId id,spdy::SpdyPriority new_priority,std::vector<ExpectedDependencyUpdate> expected)73 void TestStreamUpdate(spdy::SpdyStreamId id,
74 spdy::SpdyPriority new_priority,
75 std::vector<ExpectedDependencyUpdate> expected) {
76 auto value = dependency_state_.OnStreamUpdate(id, new_priority);
77 std::vector<Http2PriorityDependencies::DependencyUpdate> expected_value;
78 for (auto e : expected) {
79 expected_value.push_back(
80 {e.id, e.parent_id, e.weight, true /* exclusive */});
81 }
82 if (value != expected_value) {
83 ADD_FAILURE() << "OnStreamUpdate(" << id << ", " << int(new_priority)
84 << ")\n"
85 << " Value: " << value << "\n"
86 << " Expected: " << expected_value << "\n";
87 }
88 }
89
OnStreamDestruction(spdy::SpdyStreamId id)90 void OnStreamDestruction(spdy::SpdyStreamId id) {
91 dependency_state_.OnStreamDestruction(id);
92 }
93
94 private:
95 spdy::SpdyStreamId next_id_;
96 Http2PriorityDependencies dependency_state_;
97 };
98
99 // Confirm dependencies correct for entries at the same priority.
TEST_F(HttpPriorityDependencyTest,SamePriority)100 TEST_F(HttpPriorityDependencyTest, SamePriority) {
101 const spdy::SpdyStreamId first_id = GetId();
102 const spdy::SpdyStreamId second_id = GetId();
103 const spdy::SpdyStreamId third_id = GetId();
104
105 TestStreamCreation(first_id, MEDIUM, 0u);
106 TestStreamCreation(second_id, MEDIUM, first_id);
107 TestStreamCreation(third_id, MEDIUM, second_id);
108 }
109
110 // Confirm dependencies correct for entries at different priorities, increasing.
TEST_F(HttpPriorityDependencyTest,DifferentPriorityIncreasing)111 TEST_F(HttpPriorityDependencyTest, DifferentPriorityIncreasing) {
112 const spdy::SpdyStreamId first_id = GetId();
113 const spdy::SpdyStreamId second_id = GetId();
114 const spdy::SpdyStreamId third_id = GetId();
115
116 TestStreamCreation(first_id, LOWEST, 0u);
117 TestStreamCreation(second_id, MEDIUM, 0u);
118 TestStreamCreation(third_id, HIGHEST, 0u);
119 }
120
121 // Confirm dependencies correct for entries at different priorities, increasing.
TEST_F(HttpPriorityDependencyTest,DifferentPriorityDecreasing)122 TEST_F(HttpPriorityDependencyTest, DifferentPriorityDecreasing) {
123 const spdy::SpdyStreamId first_id = GetId();
124 const spdy::SpdyStreamId second_id = GetId();
125 const spdy::SpdyStreamId third_id = GetId();
126
127 TestStreamCreation(first_id, HIGHEST, 0u);
128 TestStreamCreation(second_id, MEDIUM, first_id);
129 TestStreamCreation(third_id, LOWEST, second_id);
130 }
131
132 // Confirm dependencies correct if requests are completed between before
133 // next creation.
TEST_F(HttpPriorityDependencyTest,CompletionBeforeIssue)134 TEST_F(HttpPriorityDependencyTest, CompletionBeforeIssue) {
135 const spdy::SpdyStreamId first_id = GetId();
136 const spdy::SpdyStreamId second_id = GetId();
137 const spdy::SpdyStreamId third_id = GetId();
138
139 TestStreamCreation(first_id, HIGHEST, 0u);
140 OnStreamDestruction(first_id);
141 TestStreamCreation(second_id, MEDIUM, 0u);
142 OnStreamDestruction(second_id);
143 TestStreamCreation(third_id, LOWEST, 0u);
144 }
145
146 // Confirm dependencies correct if some requests are completed between before
147 // next creation.
TEST_F(HttpPriorityDependencyTest,SomeCompletions)148 TEST_F(HttpPriorityDependencyTest, SomeCompletions) {
149 const spdy::SpdyStreamId first_id = GetId();
150 const spdy::SpdyStreamId second_id = GetId();
151 const spdy::SpdyStreamId third_id = GetId();
152
153 TestStreamCreation(first_id, HIGHEST, 0u);
154 TestStreamCreation(second_id, MEDIUM, first_id);
155 OnStreamDestruction(second_id);
156 TestStreamCreation(third_id, LOWEST, first_id);
157 }
158
159 // A more complex example parallel to a simple web page.
TEST_F(HttpPriorityDependencyTest,Complex)160 TEST_F(HttpPriorityDependencyTest, Complex) {
161 const spdy::SpdyStreamId first_id = GetId();
162 const spdy::SpdyStreamId second_id = GetId();
163 const spdy::SpdyStreamId third_id = GetId();
164 const spdy::SpdyStreamId fourth_id = GetId();
165 const spdy::SpdyStreamId fifth_id = GetId();
166 const spdy::SpdyStreamId sixth_id = GetId();
167 const spdy::SpdyStreamId seventh_id = GetId();
168 const spdy::SpdyStreamId eighth_id = GetId();
169 const spdy::SpdyStreamId nineth_id = GetId();
170 const spdy::SpdyStreamId tenth_id = GetId();
171
172 TestStreamCreation(first_id, HIGHEST, 0u);
173 TestStreamCreation(second_id, MEDIUM, first_id);
174 TestStreamCreation(third_id, MEDIUM, second_id);
175 OnStreamDestruction(first_id);
176 TestStreamCreation(fourth_id, MEDIUM, third_id);
177 TestStreamCreation(fifth_id, LOWEST, fourth_id);
178 TestStreamCreation(sixth_id, MEDIUM, fourth_id);
179 OnStreamDestruction(third_id);
180 TestStreamCreation(seventh_id, MEDIUM, sixth_id);
181 TestStreamCreation(eighth_id, LOW, seventh_id);
182 OnStreamDestruction(second_id);
183 OnStreamDestruction(fourth_id);
184 OnStreamDestruction(fifth_id);
185 OnStreamDestruction(sixth_id);
186 OnStreamDestruction(seventh_id);
187 TestStreamCreation(nineth_id, MEDIUM, 0u);
188 TestStreamCreation(tenth_id, HIGHEST, 0u);
189 }
190
191 // Confirm dependencies correct after updates with just one stream.
192 // All updates are no-ops.
TEST_F(HttpPriorityDependencyTest,UpdateSingleStream)193 TEST_F(HttpPriorityDependencyTest, UpdateSingleStream) {
194 const spdy::SpdyStreamId id = GetId();
195
196 TestStreamCreation(id, HIGHEST, 0);
197
198 std::vector<ExpectedDependencyUpdate> empty;
199 TestStreamUpdate(id, HIGHEST, empty);
200 TestStreamUpdate(id, MEDIUM, empty);
201 TestStreamUpdate(id, LOWEST, empty);
202 TestStreamUpdate(id, HIGHEST, empty);
203 }
204
205 // Confirm dependencies correct after updates with three streams.
TEST_F(HttpPriorityDependencyTest,UpdateThreeStreams)206 TEST_F(HttpPriorityDependencyTest, UpdateThreeStreams) {
207 const spdy::SpdyStreamId first_id = GetId();
208 const spdy::SpdyStreamId second_id = GetId();
209 const spdy::SpdyStreamId third_id = GetId();
210
211 TestStreamCreation(first_id, HIGHEST, 0);
212 TestStreamCreation(second_id, MEDIUM, first_id);
213 TestStreamCreation(third_id, LOWEST, second_id);
214
215 const int highest_weight = spdy::Spdy3PriorityToHttp2Weight(HIGHEST);
216 const int medium_weight = spdy::Spdy3PriorityToHttp2Weight(MEDIUM);
217 const int lowest_weight = spdy::Spdy3PriorityToHttp2Weight(LOWEST);
218
219 std::vector<ExpectedDependencyUpdate> empty;
220
221 // no-op: still at top.
222 TestStreamUpdate(first_id, HIGHEST, empty);
223
224 // no-op: still below first.
225 TestStreamUpdate(second_id, MEDIUM, empty);
226
227 // no-op: still below second.
228 TestStreamUpdate(third_id, LOWEST, empty);
229
230 // second moves to top, first moves below second.
231 TestStreamUpdate(
232 first_id, MEDIUM,
233 {{second_id, 0, medium_weight}, {first_id, second_id, medium_weight}});
234
235 // third moves to top.
236 TestStreamUpdate(third_id, HIGHEST, {{third_id, 0, highest_weight}});
237
238 // third moves to bottom.
239 TestStreamUpdate(
240 third_id, LOWEST,
241 {{second_id, 0, medium_weight}, {third_id, first_id, lowest_weight}});
242
243 // first moves to top.
244 TestStreamUpdate(
245 first_id, HIGHEST,
246 {{third_id, second_id, lowest_weight}, {first_id, 0, highest_weight}});
247 }
248
249 // A more complex example parallel to a simple web page with pushed responses.
TEST_F(HttpPriorityDependencyTest,UpdateComplex)250 TEST_F(HttpPriorityDependencyTest, UpdateComplex) {
251 const spdy::SpdyStreamId first_id = GetId();
252 const spdy::SpdyStreamId second_id = GetId(); // pushed
253 const spdy::SpdyStreamId third_id = GetId(); // pushed
254 const spdy::SpdyStreamId fourth_id = GetId();
255 const spdy::SpdyStreamId fifth_id = GetId();
256 const spdy::SpdyStreamId sixth_id = GetId();
257 const spdy::SpdyStreamId seventh_id = GetId();
258
259 TestStreamCreation(first_id, HIGHEST, 0u);
260 TestStreamCreation(second_id, LOWEST, first_id);
261 TestStreamCreation(third_id, LOWEST, second_id);
262 TestStreamCreation(fourth_id, HIGHEST, first_id);
263 TestStreamCreation(fifth_id, MEDIUM, fourth_id);
264 TestStreamCreation(sixth_id, MEDIUM, fifth_id);
265 TestStreamCreation(seventh_id, LOW, sixth_id);
266
267 const int highest_weight = spdy::Spdy3PriorityToHttp2Weight(HIGHEST);
268 const int medium_weight = spdy::Spdy3PriorityToHttp2Weight(MEDIUM);
269 const int lowest_weight = spdy::Spdy3PriorityToHttp2Weight(LOWEST);
270
271 // second matches a HIGHEST priority response.
272 // 3 moves under 7
273 // 2 moves under 4
274 TestStreamUpdate(second_id, HIGHEST,
275 {{third_id, seventh_id, lowest_weight},
276 {second_id, fourth_id, highest_weight}});
277
278 // third matches a MEDIUM priority response.
279 // 3 moves under 6
280 TestStreamUpdate(third_id, MEDIUM, {{third_id, sixth_id, medium_weight}});
281 }
282
283 } // namespace net
284