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/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