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: 17 explicit SpdyPriorityTreePeer(SpdyPriorityTree<NodeId>* tree) : tree_(tree) {} 18 19 void PropagateNodeState(NodeId node) { 20 tree_->PropagateNodeState(node); 21 } 22 23 private: 24 SpdyPriorityTree<NodeId>* tree_; 25 }; 26 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 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 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 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 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
