net/spdy/spdy_priority_tree_test.cc

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