1 // Copyright 2014 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/spdy_priority_tree.h"
6
7 #include "base/basictypes.h"
8 #include "testing/gtest/include/gtest/gtest.h"
9
10 namespace net {
11
12 namespace test {
13
14 template <typename NodeId>
15 class SpdyPriorityTreePeer {
16 public:
SpdyPriorityTreePeer(SpdyPriorityTree<NodeId> * tree)17 explicit SpdyPriorityTreePeer(SpdyPriorityTree<NodeId>* tree) : tree_(tree) {}
18
PropagateNodeState(NodeId node)19 void PropagateNodeState(NodeId node) {
20 tree_->PropagateNodeState(node);
21 }
22
23 private:
24 SpdyPriorityTree<NodeId>* tree_;
25 };
26
TEST(SpdyPriorityTreeTest,AddAndRemoveNodes)27 TEST(SpdyPriorityTreeTest, AddAndRemoveNodes) {
28 SpdyPriorityTree<uint32> tree;
29 EXPECT_EQ(1, tree.num_nodes());
30 EXPECT_TRUE(tree.NodeExists(0));
31 EXPECT_FALSE(tree.NodeExists(1));
32
33 EXPECT_TRUE(tree.AddNode(1, 0, 100, false));
34 EXPECT_EQ(2, tree.num_nodes());
35 ASSERT_TRUE(tree.NodeExists(1));
36 EXPECT_EQ(100, tree.GetWeight(1));
37 EXPECT_FALSE(tree.NodeExists(5));
38
39 EXPECT_TRUE(tree.AddNode(5, 0, 50, false));
40 // Should not be able to add a node with an id that already exists.
41 EXPECT_FALSE(tree.AddNode(5, 1, 50, false));
42 EXPECT_EQ(3, tree.num_nodes());
43 EXPECT_TRUE(tree.NodeExists(1));
44 ASSERT_TRUE(tree.NodeExists(5));
45 EXPECT_EQ(50, tree.GetWeight(5));
46 EXPECT_FALSE(tree.NodeExists(13));
47
48 EXPECT_TRUE(tree.AddNode(13, 5, 130, true));
49 EXPECT_EQ(4, tree.num_nodes());
50 EXPECT_TRUE(tree.NodeExists(1));
51 EXPECT_TRUE(tree.NodeExists(5));
52 ASSERT_TRUE(tree.NodeExists(13));
53 EXPECT_EQ(130, tree.GetWeight(13));
54 EXPECT_EQ(5u, tree.GetParent(13));
55
56 EXPECT_TRUE(tree.RemoveNode(5));
57 // Cannot remove a node that has already been removed.
58 EXPECT_FALSE(tree.RemoveNode(5));
59 EXPECT_EQ(3, tree.num_nodes());
60 EXPECT_TRUE(tree.NodeExists(1));
61 EXPECT_FALSE(tree.NodeExists(5));
62 EXPECT_TRUE(tree.NodeExists(13));
63 EXPECT_EQ(0u, tree.GetParent(13));
64
65 // The parent node 19 doesn't exist, so this should fail:
66 EXPECT_FALSE(tree.AddNode(7, 19, 70, false));
67 // This should succeed, creating node 7:
68 EXPECT_TRUE(tree.AddNode(7, 13, 70, false));
69 // Now node 7 already exists, so this should fail:
70 EXPECT_FALSE(tree.AddNode(7, 1, 70, false));
71 // Try adding a second child to node 13:
72 EXPECT_TRUE(tree.AddNode(17, 13, 170, false));
73
74 ASSERT_TRUE(tree.ValidateInvariantsForTests());
75 }
76
TEST(SpdyPriorityTreeTest,SetParent)77 TEST(SpdyPriorityTreeTest, SetParent) {
78 SpdyPriorityTree<uint32> tree;
79 tree.AddNode(1, 0, 100, false);
80 tree.AddNode(2, 1, 20, false);
81 tree.AddNode(3, 2, 30, false);
82 tree.AddNode(5, 3, 50, false);
83 tree.AddNode(7, 5, 70, false);
84 tree.AddNode(9, 7, 90, false);
85 tree.AddNode(11, 0, 200, false);
86 tree.AddNode(13, 11, 130, false);
87 // We can't set the parent of a nonexistent node, or set the parent of an
88 // existing node to a nonexistent node.
89 EXPECT_FALSE(tree.SetParent(99, 13, false));
90 EXPECT_FALSE(tree.SetParent(5, 99, false));
91 // We should be able to add multiple children to nodes.
92 EXPECT_TRUE(tree.SetParent(13, 7, false));
93 EXPECT_TRUE(tree.SetParent(3, 11, false));
94 // We should adjust the tree if a new dependency would create a cycle.
95 EXPECT_TRUE(tree.SetParent(11, 13, false));
96 EXPECT_TRUE(tree.SetParent(1, 9, false));
97 EXPECT_TRUE(tree.SetParent(3, 9, false));
98 // Test dependency changes.
99 EXPECT_TRUE(tree.HasChild(5, 7));
100 EXPECT_TRUE(tree.SetParent(7, 13, false));
101 EXPECT_EQ(13u, tree.GetParent(7));
102 EXPECT_TRUE(tree.HasChild(13, 7));
103
104 EXPECT_TRUE(tree.SetParent(1, 9, false));
105 EXPECT_EQ(9u, tree.GetParent(1));
106 EXPECT_TRUE(tree.HasChild(9, 1));
107 // Setting the parent of a node to its same parent should be a no-op.
108 EXPECT_EQ(1u, tree.GetParent(2));
109 EXPECT_TRUE(tree.HasChild(1, 2));
110 EXPECT_TRUE(tree.SetParent(2, 1, true));
111 EXPECT_EQ(1u, tree.GetParent(2));
112 EXPECT_TRUE(tree.HasChild(1, 2));
113
114 ASSERT_TRUE(tree.ValidateInvariantsForTests());
115 }
116
TEST(SpdyPriorityTreeTest,BlockAndUnblock)117 TEST(SpdyPriorityTreeTest, BlockAndUnblock) {
118 /* Create the tree.
119
120 0
121 /|\
122 1 2 3
123 /| | \
124 4 5 6 7
125 /| |\ \ |\
126 8 91011121314
127 / \
128 15 16
129
130 */
131 SpdyPriorityTree<uint32> tree;
132 SpdyPriorityTreePeer<uint32> tree_peer(&tree);
133 tree.AddNode(1, 0, 100, false);
134 tree.AddNode(2, 0, 100, false);
135 tree.AddNode(3, 0, 100, false);
136 tree.AddNode(4, 1, 100, false);
137 tree.AddNode(5, 1, 100, false);
138 tree.AddNode(8, 4, 100, false);
139 tree.AddNode(9, 4, 100, false);
140 tree.AddNode(10, 5, 100, false);
141 tree.AddNode(11, 5, 100, false);
142 tree.AddNode(15, 8, 100, false);
143 tree.AddNode(16, 8, 100, false);
144 tree.AddNode(12, 2, 100, false);
145 tree.AddNode(6, 2, 100, true);
146 tree.AddNode(7, 0, 100, false);
147 tree.AddNode(13, 7, 100, true);
148 tree.AddNode(14, 7, 100, false);
149 tree.SetParent(7, 3, false);
150 EXPECT_EQ(0u, tree.GetParent(1));
151 EXPECT_EQ(0u, tree.GetParent(2));
152 EXPECT_EQ(0u, tree.GetParent(3));
153 EXPECT_EQ(1u, tree.GetParent(4));
154 EXPECT_EQ(1u, tree.GetParent(5));
155 EXPECT_EQ(2u, tree.GetParent(6));
156 EXPECT_EQ(3u, tree.GetParent(7));
157 EXPECT_EQ(4u, tree.GetParent(8));
158 EXPECT_EQ(4u, tree.GetParent(9));
159 EXPECT_EQ(5u, tree.GetParent(10));
160 EXPECT_EQ(5u, tree.GetParent(11));
161 EXPECT_EQ(6u, tree.GetParent(12));
162 EXPECT_EQ(7u, tree.GetParent(13));
163 EXPECT_EQ(7u, tree.GetParent(14));
164 EXPECT_EQ(8u, tree.GetParent(15));
165 EXPECT_EQ(8u, tree.GetParent(16));
166 ASSERT_TRUE(tree.ValidateInvariantsForTests());
167
168 EXPECT_EQ(tree.FindNode(0)->total_child_weights,
169 tree.FindNode(1)->weight +
170 tree.FindNode(2)->weight +
171 tree.FindNode(3)->weight);
172 EXPECT_EQ(tree.FindNode(3)->total_child_weights,
173 tree.FindNode(7)->weight);
174 EXPECT_EQ(tree.FindNode(7)->total_child_weights,
175 tree.FindNode(13)->weight + tree.FindNode(14)->weight);
176 EXPECT_EQ(tree.FindNode(13)->total_child_weights, 0);
177 EXPECT_EQ(tree.FindNode(14)->total_child_weights, 0);
178
179 // Set all nodes ready to write.
180 EXPECT_TRUE(tree.SetReady(1, true));
181 EXPECT_TRUE(tree.SetReady(2, true));
182 EXPECT_TRUE(tree.SetReady(3, true));
183 EXPECT_TRUE(tree.SetReady(4, true));
184 EXPECT_TRUE(tree.SetReady(5, true));
185 EXPECT_TRUE(tree.SetReady(6, true));
186 EXPECT_TRUE(tree.SetReady(7, true));
187 EXPECT_TRUE(tree.SetReady(8, true));
188 EXPECT_TRUE(tree.SetReady(9, true));
189 EXPECT_TRUE(tree.SetReady(10, true));
190 EXPECT_TRUE(tree.SetReady(11, true));
191 EXPECT_TRUE(tree.SetReady(12, true));
192 EXPECT_TRUE(tree.SetReady(13, true));
193 EXPECT_TRUE(tree.SetReady(14, true));
194 EXPECT_TRUE(tree.SetReady(15, true));
195 EXPECT_TRUE(tree.SetReady(16, true));
196
197 // Number of readable child weights should not change because
198 // 7 has unblocked children.
199 tree.SetBlocked(7, true);
200 tree_peer.PropagateNodeState(kRootNodeId);
201 EXPECT_EQ(tree.FindNode(3)->total_child_weights,
202 tree.FindNode(3)->total_writeable_child_weights);
203
204 // Readable children for 7 should decrement.
205 // Number of readable child weights for 3 still should not change.
206 tree.SetBlocked(13, true);
207 tree_peer.PropagateNodeState(kRootNodeId);
208 EXPECT_EQ(tree.FindNode(3)->total_child_weights,
209 tree.FindNode(3)->total_writeable_child_weights);
210 EXPECT_EQ(tree.FindNode(14)->weight,
211 tree.FindNode(7)->total_writeable_child_weights);
212
213 // Once 14 becomes blocked, readable children for 7 and 3 should both be
214 // decremented. Total readable weights at the root should still be the same
215 // because 3 is still writeable.
216 tree.SetBlocked(14, true);
217 tree_peer.PropagateNodeState(kRootNodeId);
218 EXPECT_EQ(0, tree.FindNode(3)->total_writeable_child_weights);
219 EXPECT_EQ(0, tree.FindNode(7)->total_writeable_child_weights);
220 EXPECT_EQ(tree.FindNode(0)->total_child_weights,
221 tree.FindNode(1)->weight +
222 tree.FindNode(2)->weight +
223 tree.FindNode(3)->weight);
224
225 // And now the root should be decremented as well.
226 tree.SetBlocked(3, true);
227 tree_peer.PropagateNodeState(kRootNodeId);
228 EXPECT_EQ(tree.FindNode(1)->weight + tree.FindNode(2)->weight,
229 tree.FindNode(0)->total_writeable_child_weights);
230
231 // Unblocking 7 should propagate all the way up to the root.
232 tree.SetBlocked(7, false);
233 tree_peer.PropagateNodeState(kRootNodeId);
234 EXPECT_EQ(tree.FindNode(0)->total_writeable_child_weights,
235 tree.FindNode(1)->weight +
236 tree.FindNode(2)->weight +
237 tree.FindNode(3)->weight);
238 EXPECT_EQ(tree.FindNode(3)->total_writeable_child_weights,
239 tree.FindNode(7)->weight);
240 EXPECT_EQ(0, tree.FindNode(7)->total_writeable_child_weights);
241
242 // Ditto for reblocking 7.
243 tree.SetBlocked(7, true);
244 tree_peer.PropagateNodeState(kRootNodeId);
245 EXPECT_EQ(tree.FindNode(0)->total_writeable_child_weights,
246 tree.FindNode(1)->weight + tree.FindNode(2)->weight);
247 EXPECT_EQ(0, tree.FindNode(3)->total_writeable_child_weights);
248 EXPECT_EQ(0, tree.FindNode(7)->total_writeable_child_weights);
249 ASSERT_TRUE(tree.ValidateInvariantsForTests());
250 }
251
TEST(SpdyPriorityTreeTest,GetPriorityList)252 TEST(SpdyPriorityTreeTest, GetPriorityList) {
253 typedef uint32 SpdyStreamId;
254 typedef std::pair<SpdyStreamId, float> PriorityNode;
255 typedef std::vector<PriorityNode> PriorityList;
256
257 PriorityList expected_list;
258 PriorityList priority_list;
259
260 /* Create the tree.
261
262 0
263 /|\
264 1 2 3
265 /| |\
266 4 5 6 7
267 /
268 8
269
270 */
271 SpdyPriorityTree<uint32> tree;
272 tree.AddNode(1, 0, 10, false);
273 tree.AddNode(2, 0, 20, false);
274 tree.AddNode(3, 0, 30, false);
275 tree.AddNode(4, 1, 10, false);
276 tree.AddNode(5, 1, 90, false);
277 tree.AddNode(6, 2, 10, false);
278 tree.AddNode(7, 2, 10, false);
279 tree.AddNode(8, 4, 256, false);
280
281 // Set all nodes ready to write.
282 EXPECT_TRUE(tree.SetReady(1, true));
283 EXPECT_TRUE(tree.SetReady(2, true));
284 EXPECT_TRUE(tree.SetReady(3, true));
285 EXPECT_TRUE(tree.SetReady(4, true));
286 EXPECT_TRUE(tree.SetReady(5, true));
287 EXPECT_TRUE(tree.SetReady(6, true));
288 EXPECT_TRUE(tree.SetReady(7, true));
289 EXPECT_TRUE(tree.SetReady(8, true));
290
291 expected_list.push_back(PriorityNode(3, 1.0/2.0));
292 expected_list.push_back(PriorityNode(2, 1.0/3.0));
293 expected_list.push_back(PriorityNode(1, 1.0/6.0));
294 priority_list = tree.GetPriorityList();
295 EXPECT_EQ(expected_list, priority_list);
296
297 // Check that the list updates as expected when a node gets blocked.
298 EXPECT_TRUE(tree.SetReady(1, false));
299 expected_list.clear();
300 expected_list.push_back(PriorityNode(3, 1.0/2.0));
301 expected_list.push_back(PriorityNode(2, 1.0/3.0));
302 expected_list.push_back(PriorityNode(5, 0.9*1.0/6.0));
303 expected_list.push_back(PriorityNode(4, 0.1*1.0/6.0));
304 priority_list = tree.GetPriorityList();
305 EXPECT_EQ(expected_list, priority_list);
306
307 // Block multiple levels of nodes.
308 EXPECT_TRUE(tree.SetReady(4, false));
309 EXPECT_TRUE(tree.SetReady(5, false));
310 expected_list.clear();
311 expected_list.push_back(PriorityNode(3, 1.0/2.0));
312 expected_list.push_back(PriorityNode(2, 1.0/3.0));
313 expected_list.push_back(PriorityNode(8, 1.0/6.0));
314 priority_list = tree.GetPriorityList();
315 EXPECT_EQ(expected_list, priority_list);
316
317 // Remove a node from the tree to make sure priorities
318 // get redistributed accordingly.
319 EXPECT_TRUE(tree.RemoveNode(1));
320 expected_list.clear();
321 expected_list.push_back(PriorityNode(3, 30.0/51.0));
322 expected_list.push_back(PriorityNode(2, 20.0/51.0));
323 expected_list.push_back(PriorityNode(8, 1.0/51.0));
324 priority_list = tree.GetPriorityList();
325 EXPECT_EQ(expected_list, priority_list);
326
327 // Block an entire subtree.
328 EXPECT_TRUE(tree.SetReady(8, false));
329 expected_list.clear();
330 expected_list.push_back(PriorityNode(3, 0.6));
331 expected_list.push_back(PriorityNode(2, 0.4));
332 priority_list = tree.GetPriorityList();
333 EXPECT_EQ(expected_list, priority_list);
334
335 // Unblock previously blocked nodes.
336 EXPECT_TRUE(tree.SetReady(4, true));
337 EXPECT_TRUE(tree.SetReady(5, true));
338 expected_list.clear();
339 expected_list.push_back(PriorityNode(3, 1.0/2.0));
340 expected_list.push_back(PriorityNode(2, 1.0/3.0));
341 expected_list.push_back(PriorityNode(5, 9.0/60.0));
342 expected_list.push_back(PriorityNode(4, 1.0/60.0));
343 priority_list = tree.GetPriorityList();
344 EXPECT_EQ(expected_list, priority_list);
345
346 // Blocked nodes in multiple subtrees.
347 EXPECT_TRUE(tree.SetReady(2, false));
348 EXPECT_TRUE(tree.SetReady(6, false));
349 EXPECT_TRUE(tree.SetReady(7, false));
350 expected_list.clear();
351 expected_list.push_back(PriorityNode(3, 3.0/4.0));
352 expected_list.push_back(PriorityNode(5, 9.0/40.0));
353 expected_list.push_back(PriorityNode(4, 1.0/40.0));
354 priority_list = tree.GetPriorityList();
355 EXPECT_EQ(expected_list, priority_list);
356 }
357
TEST(SpdyPriorityTreeTest,CalculateRoundedWeights)358 TEST(SpdyPriorityTreeTest, CalculateRoundedWeights) {
359 typedef uint32 SpdyStreamId;
360 typedef std::pair<SpdyStreamId, float> PriorityNode;
361 typedef std::vector<PriorityNode> PriorityList;
362
363 PriorityList expected_list;
364 PriorityList priority_list;
365
366 /* Create the tree.
367
368 0
369 / \
370 1 2
371 //|\ |\
372 83 4 5 6 7
373 */
374 SpdyPriorityTree<uint32> tree;
375 tree.AddNode(3, 0, 100, false);
376 tree.AddNode(4, 0, 100, false);
377 tree.AddNode(5, 0, 100, false);
378 tree.AddNode(1, 0, 10, true);
379 tree.AddNode(2, 0, 5, false);
380 tree.AddNode(6, 2, 1, false);
381 tree.AddNode(7, 2, 1, false);
382 tree.AddNode(8, 1, 1, false);
383
384 // Remove higher-level nodes.
385 tree.RemoveNode(1);
386 tree.RemoveNode(2);
387
388 // 3.3 rounded down = 3.
389 EXPECT_EQ(3, tree.GetWeight(3));
390 EXPECT_EQ(3, tree.GetWeight(4));
391 EXPECT_EQ(3, tree.GetWeight(5));
392 // 2.5 rounded up = 3.
393 EXPECT_EQ(3, tree.GetWeight(6));
394 EXPECT_EQ(3, tree.GetWeight(7));
395 // 0 is not a valid weight, so round up to 1.
396 EXPECT_EQ(1, tree.GetWeight(8));
397 }
398 } // namespace test
399 } // namespace gfe_spdy
400