net/spdy/spdy_priority_forest_test.cc

   1 // Copyright (c) 2013 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_forest.h"
   6
   7 #include "base/basictypes.h"
   8 #include "testing/gtest/include/gtest/gtest.h"
   9
  10 namespace net {
  11
  12 TEST(SpdyPriorityForestTest, AddAndRemoveNodes) {
  13   SpdyPriorityForest<uint32,int16> forest;
  14   EXPECT_EQ(0, forest.num_nodes());
  15   EXPECT_FALSE(forest.NodeExists(1));
  16
  17   EXPECT_TRUE(forest.AddRootNode(1, 1000));
  18   EXPECT_EQ(1, forest.num_nodes());
  19   ASSERT_TRUE(forest.NodeExists(1));
  20   EXPECT_EQ(1000, forest.GetPriority(1));
  21   EXPECT_FALSE(forest.NodeExists(5));
  22
  23   EXPECT_TRUE(forest.AddRootNode(5, 50));
  24   EXPECT_FALSE(forest.AddRootNode(5, 500));
  25   EXPECT_EQ(2, forest.num_nodes());
  26   EXPECT_TRUE(forest.NodeExists(1));
  27   ASSERT_TRUE(forest.NodeExists(5));
  28   EXPECT_EQ(50, forest.GetPriority(5));
  29   EXPECT_FALSE(forest.NodeExists(13));
  30
  31   EXPECT_TRUE(forest.AddRootNode(13, 130));
  32   EXPECT_EQ(3, forest.num_nodes());
  33   EXPECT_TRUE(forest.NodeExists(1));
  34   EXPECT_TRUE(forest.NodeExists(5));
  35   ASSERT_TRUE(forest.NodeExists(13));
  36   EXPECT_EQ(130, forest.GetPriority(13));
  37
  38   EXPECT_TRUE(forest.RemoveNode(5));
  39   EXPECT_FALSE(forest.RemoveNode(5));
  40   EXPECT_EQ(2, forest.num_nodes());
  41   EXPECT_TRUE(forest.NodeExists(1));
  42   EXPECT_FALSE(forest.NodeExists(5));
  43   EXPECT_TRUE(forest.NodeExists(13));
  44
  45   // The parent node 19 doesn't exist, so this should fail:
  46   EXPECT_FALSE(forest.AddNonRootNode(7, 19, false));
  47   // This should succed, creating node 7:
  48   EXPECT_TRUE(forest.AddNonRootNode(7, 13, false));
  49   // Now node 7 already exists, so this should fail:
  50   EXPECT_FALSE(forest.AddNonRootNode(7, 1, false));
  51   // Node 13 already has a child (7), so this should fail:
  52   EXPECT_FALSE(forest.AddNonRootNode(17, 13, false));
  53
  54   ASSERT_TRUE(forest.ValidateInvariantsForTests());
  55 }
  56
  57 TEST(SpdyPriorityForestTest, SetParent) {
  58   SpdyPriorityForest<uint32,int16> forest;
  59   forest.AddRootNode(1, 1000);
  60   forest.AddNonRootNode(2, 1, false);
  61   forest.AddNonRootNode(3, 2, false);
  62   forest.AddNonRootNode(5, 3, false);
  63   forest.AddNonRootNode(7, 5, false);
  64   forest.AddNonRootNode(9, 7, false);
  65   forest.AddRootNode(11, 2000);
  66   forest.AddNonRootNode(13, 11, false);
  67   // We can't set the parent of a nonexistent node, or set the parent of an
  68   // existing node to a nonexistent node.
  69   EXPECT_FALSE(forest.SetParent(99, 13, false));
  70   EXPECT_FALSE(forest.SetParent(5, 99, false));
  71   // We can't make a node a child a node that already has a child:
  72   EXPECT_FALSE(forest.SetParent(13, 7, false));
  73   EXPECT_FALSE(forest.SetParent(3, 11, false));
  74   // These would create cycles:
  75   EXPECT_FALSE(forest.SetParent(11, 13, false));
  76   EXPECT_FALSE(forest.SetParent(1, 9, false));
  77   EXPECT_FALSE(forest.SetParent(3, 9, false));
  78   // But this change is legit:
  79   EXPECT_EQ(7u, forest.GetChild(5));
  80   EXPECT_TRUE(forest.SetParent(7, 13, false));
  81   EXPECT_EQ(0u, forest.GetChild(5));
  82   EXPECT_EQ(13u, forest.GetParent(7));
  83   EXPECT_EQ(7u, forest.GetChild(13));
  84   // So is this change (now that 9 is no longer a descendant of 1):
  85   EXPECT_TRUE(forest.SetParent(1, 9, false));
  86   EXPECT_EQ(9u, forest.GetParent(1));
  87   EXPECT_EQ(1u, forest.GetChild(9));
  88   // We must allow setting the parent of a node to its same parent (even though
  89   // that parent of course has a child already), so that we can change
  90   // orderedness.
  91   EXPECT_EQ(1u, forest.GetParent(2));
  92   EXPECT_EQ(2u, forest.GetChild(1));
  93   EXPECT_FALSE(forest.IsNodeUnordered(2));
  94   EXPECT_TRUE(forest.SetParent(2, 1, true));
  95   EXPECT_EQ(1u, forest.GetParent(2));
  96   EXPECT_EQ(2u, forest.GetChild(1));
  97   EXPECT_TRUE(forest.IsNodeUnordered(2));
  98
  99   ASSERT_TRUE(forest.ValidateInvariantsForTests());
 100 }
 101
 102 TEST(SpdyPriorityForestTest, RemoveNodesFromMiddleOfChain) {
 103   SpdyPriorityForest<uint32,int16> forest;
 104   forest.AddRootNode(1, 1000);
 105   forest.AddNonRootNode(2, 1, false);
 106   forest.AddNonRootNode(3, 2, true);
 107   forest.AddNonRootNode(5, 3, false);
 108   forest.AddNonRootNode(7, 5, true);
 109   forest.AddNonRootNode(9, 7, true);
 110
 111   // Remove a node from the middle, with unordered links on both sides.  The
 112   // new merged link should also be unordered.
 113   EXPECT_TRUE(forest.NodeExists(7));
 114   EXPECT_EQ(7u, forest.GetChild(5));
 115   EXPECT_EQ(7u, forest.GetParent(9));
 116   EXPECT_TRUE(forest.IsNodeUnordered(9));
 117   EXPECT_TRUE(forest.RemoveNode(7));
 118   EXPECT_FALSE(forest.NodeExists(7));
 119   EXPECT_EQ(9u, forest.GetChild(5));
 120   EXPECT_EQ(5u, forest.GetParent(9));
 121   EXPECT_TRUE(forest.IsNodeUnordered(9));
 122
 123   // Remove another node from the middle, with an unordered link on only one
 124   // side.  The new merged link should be ordered.
 125   EXPECT_TRUE(forest.NodeExists(2));
 126   EXPECT_EQ(2u, forest.GetChild(1));
 127   EXPECT_EQ(2u, forest.GetParent(3));
 128   EXPECT_FALSE(forest.IsNodeUnordered(2));
 129   EXPECT_TRUE(forest.IsNodeUnordered(3));
 130   EXPECT_TRUE(forest.RemoveNode(2));
 131   EXPECT_FALSE(forest.NodeExists(2));
 132   EXPECT_EQ(3u, forest.GetChild(1));
 133   EXPECT_EQ(1u, forest.GetParent(3));
 134   EXPECT_FALSE(forest.IsNodeUnordered(3));
 135
 136   // Try removing the root.
 137   EXPECT_TRUE(forest.NodeExists(1));
 138   EXPECT_EQ(0u, forest.GetParent(1));
 139   EXPECT_EQ(1000, forest.GetPriority(1));
 140   EXPECT_EQ(1u, forest.GetParent(3));
 141   EXPECT_EQ(0, forest.GetPriority(3));
 142   EXPECT_TRUE(forest.RemoveNode(1));
 143   EXPECT_FALSE(forest.NodeExists(1));
 144   EXPECT_EQ(0u, forest.GetParent(3));
 145   EXPECT_EQ(1000, forest.GetPriority(3));
 146
 147   // Now try removing the tail.
 148   EXPECT_TRUE(forest.NodeExists(9));
 149   EXPECT_EQ(9u, forest.GetChild(5));
 150   EXPECT_TRUE(forest.RemoveNode(9));
 151   EXPECT_FALSE(forest.NodeExists(9));
 152   EXPECT_EQ(0u, forest.GetChild(5));
 153
 154   ASSERT_TRUE(forest.ValidateInvariantsForTests());
 155 }
 156
 157 TEST(SpdyPriorityForestTest, MergeOrderedAndUnorderedLinks1) {
 158   SpdyPriorityForest<uint32,int16> forest;
 159   forest.AddRootNode(1, 1000);
 160   forest.AddNonRootNode(2, 1, true);
 161   forest.AddNonRootNode(3, 2, false);
 162
 163   EXPECT_EQ(2u, forest.GetChild(1));
 164   EXPECT_EQ(3u, forest.GetChild(2));
 165   EXPECT_EQ(1u, forest.GetParent(2));
 166   EXPECT_EQ(2u, forest.GetParent(3));
 167   EXPECT_TRUE(forest.IsNodeUnordered(2));
 168   EXPECT_FALSE(forest.IsNodeUnordered(3));
 169   EXPECT_TRUE(forest.RemoveNode(2));
 170   EXPECT_FALSE(forest.NodeExists(2));
 171   EXPECT_EQ(3u, forest.GetChild(1));
 172   EXPECT_EQ(1u, forest.GetParent(3));
 173   EXPECT_FALSE(forest.IsNodeUnordered(3));
 174
 175   ASSERT_TRUE(forest.ValidateInvariantsForTests());
 176 }
 177
 178 TEST(SpdyPriorityForestTest, MergeOrderedAndUnorderedLinks2) {
 179   SpdyPriorityForest<uint32,int16> forest;
 180   forest.AddRootNode(1, 1000);
 181   forest.AddNonRootNode(2, 1, false);
 182   forest.AddNonRootNode(3, 2, true);
 183
 184   EXPECT_EQ(2u, forest.GetChild(1));
 185   EXPECT_EQ(3u, forest.GetChild(2));
 186   EXPECT_EQ(1u, forest.GetParent(2));
 187   EXPECT_EQ(2u, forest.GetParent(3));
 188   EXPECT_FALSE(forest.IsNodeUnordered(2));
 189   EXPECT_TRUE(forest.IsNodeUnordered(3));
 190   EXPECT_TRUE(forest.RemoveNode(2));
 191   EXPECT_FALSE(forest.NodeExists(2));
 192   EXPECT_EQ(3u, forest.GetChild(1));
 193   EXPECT_EQ(1u, forest.GetParent(3));
 194   EXPECT_FALSE(forest.IsNodeUnordered(3));
 195
 196   ASSERT_TRUE(forest.ValidateInvariantsForTests());
 197 }
 198
 199 TEST(SpdyPriorityForestTest, WeightedSelectionOfForests) {
 200   SpdyPriorityForest<uint32,int16> forest;
 201   forest.AddRootNode(1, 10);
 202   forest.AddRootNode(3, 20);
 203   forest.AddRootNode(5, 70);
 204   EXPECT_EQ(70, forest.GetPriority(5));
 205   EXPECT_TRUE(forest.SetPriority(5, 40));
 206   EXPECT_FALSE(forest.SetPriority(7, 80));
 207   EXPECT_EQ(40, forest.GetPriority(5));
 208   forest.AddNonRootNode(7, 3, false);
 209   EXPECT_FALSE(forest.IsMarkedReadyToRead(1));
 210   EXPECT_TRUE(forest.MarkReadyToRead(1));
 211   EXPECT_TRUE(forest.IsMarkedReadyToRead(1));
 212   EXPECT_TRUE(forest.MarkReadyToRead(5));
 213   EXPECT_TRUE(forest.MarkReadyToRead(7));
 214   EXPECT_FALSE(forest.MarkReadyToRead(99));
 215
 216   int counts[8] = {0};
 217   for (int i = 0; i < 7000; ++i) {
 218     const uint32 node_id = forest.NextNodeToRead();
 219     ASSERT_TRUE(node_id == 1 || node_id == 5 || node_id == 7)
 220         << "node_id is " << node_id;
 221     ++counts[node_id];
 222   }
 223
 224   // In theory, these could fail even if the weighted random selection is
 225   // implemented correctly, but it's very unlikely.
 226   EXPECT_GE(counts[1],  800); EXPECT_LE(counts[1], 1200);
 227   EXPECT_GE(counts[7], 1600); EXPECT_LE(counts[7], 2400);
 228   EXPECT_GE(counts[5], 3200); EXPECT_LE(counts[5], 4800);
 229
 230   // If we unmark all but one node, then we know for sure that that node will
 231   // be selected next.
 232   EXPECT_TRUE(forest.MarkNoLongerReadyToRead(1));
 233   EXPECT_TRUE(forest.MarkNoLongerReadyToRead(7));
 234   EXPECT_FALSE(forest.MarkNoLongerReadyToRead(99));
 235   EXPECT_EQ(5u, forest.NextNodeToRead());
 236
 237   ASSERT_TRUE(forest.ValidateInvariantsForTests());
 238 }
 239
 240 TEST(SpdyPriorityForestTest, SelectionBetweenUnorderedNodes) {
 241   SpdyPriorityForest<uint32,int16> forest;
 242   forest.AddRootNode(1, 1000);
 243   forest.AddNonRootNode(2, 1, false);
 244   forest.AddNonRootNode(3, 2, true);
 245   forest.AddNonRootNode(4, 3, true);
 246   forest.AddNonRootNode(5, 4, true);
 247   forest.AddNonRootNode(6, 5, true);
 248   forest.AddNonRootNode(7, 6, false);
 249   EXPECT_FALSE(forest.IsMarkedReadyToWrite(2));
 250   EXPECT_TRUE(forest.MarkReadyToWrite(2));
 251   EXPECT_TRUE(forest.IsMarkedReadyToWrite(2));
 252   EXPECT_TRUE(forest.MarkReadyToWrite(4));
 253   EXPECT_TRUE(forest.MarkReadyToWrite(6));
 254   EXPECT_TRUE(forest.MarkReadyToWrite(7));
 255   EXPECT_FALSE(forest.MarkReadyToWrite(99));
 256
 257   int counts[8] = {0};
 258   for (int i = 0; i < 6000; ++i) {
 259     const uint32 node_id = forest.NextNodeToWrite();
 260     ASSERT_TRUE(node_id == 2 || node_id == 4 || node_id == 6)
 261         << "node_id is " << node_id;
 262     ++counts[node_id];
 263   }
 264
 265   // In theory, these could fail even if the random selection is implemented
 266   // correctly, but it's very unlikely.
 267   EXPECT_GE(counts[2], 1600); EXPECT_LE(counts[2], 2400);
 268   EXPECT_GE(counts[4], 1600); EXPECT_LE(counts[4], 2400);
 269   EXPECT_GE(counts[6], 1600); EXPECT_LE(counts[6], 2400);
 270
 271   // Once we unmark that group of nodes, the next node up should be node 7,
 272   // which has an ordered dependency on said group.
 273   EXPECT_TRUE(forest.MarkNoLongerReadyToWrite(2));
 274   EXPECT_TRUE(forest.MarkNoLongerReadyToWrite(4));
 275   EXPECT_TRUE(forest.MarkNoLongerReadyToWrite(6));
 276   EXPECT_FALSE(forest.MarkNoLongerReadyToWrite(99));
 277   EXPECT_EQ(7u, forest.NextNodeToWrite());
 278
 279   ASSERT_TRUE(forest.ValidateInvariantsForTests());
 280 }
 281
 282 }  // namespace net