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