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