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 283
