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 #ifndef NET_SPDY_SPDY_PRIORITY_FOREST_H_ 6 #define NET_SPDY_SPDY_PRIORITY_FOREST_H_ 7 8 #include <map> 9 #include <set> 10 11 #include "base/basictypes.h" 12 #include "base/containers/hash_tables.h" 13 #include "base/logging.h" 14 #include "base/memory/scoped_ptr.h" 15 #include "base/rand_util.h" 16 17 namespace net { 18 19 // This data structure implements the SPDY prioriziation data structures 20 // defined in this document: http://go/spdy4-prioritization 21 // 22 // Nodes can be added and removed, and dependencies between them defined. Each 23 // node can have at most one parent and at most one child (forming a list), but 24 // there can be multiple lists, with each list root having its own priority. 25 // Individual nodes can also be marked as ready to read/write, and then the 26 // whole structure can be queried to pick the next node to read/write out of 27 // those ready. 28 // 29 // The NodeId and Priority types must be POD that support comparison (most 30 // likely, they will be numbers). 31 template <typename NodeId, typename Priority> 32 class SpdyPriorityForest { 33 public: 34 SpdyPriorityForest(); 35 ~SpdyPriorityForest(); 36 37 // Return the number of nodes currently in the forest. 38 int num_nodes() const; 39 40 // Return true if the forest contains a node with the given ID. 41 bool NodeExists(NodeId node_id) const; 42 43 // Add a new root node to the forest, with the given priority. Returns true 44 // on success, or false if the node_id already exists within the forest. 45 bool AddRootNode(NodeId node_id, Priority priority); 46 47 // Add a new node to the forest, with the given parent. Returns true on 48 // success. Returns false and has no effect if the new node already exists, 49 // or if the parent doesn't exist, or if the parent already has a child. 50 bool AddNonRootNode(NodeId node_id, NodeId parent_id, bool unordered); 51 52 // Remove an existing node from the forest. Returns true on success, or 53 // false if the node doesn't exist. 54 bool RemoveNode(NodeId node_id); 55 56 // Get the priority of the given node. If the node doesn't exist, or is not 57 // a root node (and thus has no priority), returns Priority(). 58 Priority GetPriority(NodeId node_id) const; 59 60 // Get the parent of the given node. If the node doesn't exist, or is a root 61 // node (and thus has no parent), returns NodeId(). 62 NodeId GetParent(NodeId node_id) const; 63 64 // Determine if the given node is unordered with respect to its parent. If 65 // the node doesn't exist, or is a root node (and thus has no parent), 66 // returns false. 67 bool IsNodeUnordered(NodeId node_id) const; 68 69 // Get the child of the given node. If the node doesn't exist, or has no 70 // child, returns NodeId(). 71 NodeId GetChild(NodeId node_id) const; 72 73 // Set the priority of the given node. If the node was not already a root 74 // node, this makes it a root node. Returns true on success, or false if the 75 // node doesn't exist. 76 bool SetPriority(NodeId node_id, Priority priority); 77 78 // Set the parent of the given node. If the node was a root node, this makes 79 // it no longer a root. Returns true on success. Returns false and has no 80 // effect if (1) the node and/or the parent doesn't exist, (2) the new parent 81 // already has a different child than the node, or (3) if the new parent is a 82 // descendant of the node (so this would have created a cycle). 83 bool SetParent(NodeId node_id, NodeId parent_id, bool unordered); 84 85 // Check if a node is marked as ready to read. Returns false if the node 86 // doesn't exist. 87 bool IsMarkedReadyToRead(NodeId node_id) const; 88 // Mark the node as ready or not ready to read. Returns true on success, or 89 // false if the node doesn't exist. 90 bool MarkReadyToRead(NodeId node_id); 91 bool MarkNoLongerReadyToRead(NodeId node_id); 92 // Return the ID of the next node that we should read, or return NodeId() if 93 // no node in the forest is ready to read. 94 NodeId NextNodeToRead(); 95 96 // Check if a node is marked as ready to write. Returns false if the node 97 // doesn't exist. 98 bool IsMarkedReadyToWrite(NodeId node_id) const; 99 // Mark the node as ready or not ready to write. Returns true on success, or 100 // false if the node doesn't exist. 101 bool MarkReadyToWrite(NodeId node_id); 102 bool MarkNoLongerReadyToWrite(NodeId node_id); 103 // Return the ID of the next node that we should write, or return NodeId() if 104 // no node in the forest is ready to write. 105 NodeId NextNodeToWrite(); 106 107 // Return true if all internal invariants hold (useful for unit tests). 108 // Unless there are bugs, this should always return true. 109 bool ValidateInvariantsForTests() const; 110 111 private: 112 enum NodeType { ROOT_NODE, NONROOT_ORDERED, NONROOT_UNORDERED }; 113 struct Node { 114 Node() : type(ROOT_NODE), flags(0), child() { 115 depends_on.priority = Priority(); 116 } 117 NodeType type; 118 unsigned int flags; // bitfield of flags 119 union { 120 Priority priority; // used for root nodes 121 NodeId parent_id; // used for non-root nodes 122 } depends_on; 123 NodeId child; // node ID of child (or NodeId() for no child) 124 }; 125 126 typedef base::hash_map<NodeId, Node> NodeMap; 127 128 // Constants for the Node.flags bitset: 129 // kReadToRead: set for nodes that are ready for reading 130 static const unsigned int kReadyToRead = (1 << 0); 131 // kReadToWrite: set for nodes that are ready for writing 132 static const unsigned int kReadyToWrite = (1 << 1); 133 134 // Common code for IsMarkedReadyToRead and IsMarkedReadyToWrite. 135 bool IsMarked(NodeId node_id, unsigned int flag) const; 136 // Common code for MarkReadyToRead and MarkReadyToWrite. 137 bool Mark(NodeId node_id, unsigned int flag); 138 // Common code for MarkNoLongerReadyToRead and MarkNoLongerReadyToWrite. 139 bool Unmark(NodeId node_id, unsigned int flag); 140 // Common code for NextNodeToRead and NextNodeToWrite; 141 NodeId FirstMarkedNode(unsigned int flag); 142 // Get the given node, or return NULL if it doesn't exist. 143 const Node* FindNode(NodeId node_id) const; 144 145 NodeMap all_nodes_; // maps from node IDs to Node objects 146 147 DISALLOW_COPY_AND_ASSIGN(SpdyPriorityForest); 148 }; 149 150 template <typename NodeId, typename Priority> 151 SpdyPriorityForest<NodeId, Priority>::SpdyPriorityForest() {} 152 153 template <typename NodeId, typename Priority> 154 SpdyPriorityForest<NodeId, Priority>::~SpdyPriorityForest() {} 155 156 template <typename NodeId, typename Priority> 157 int SpdyPriorityForest<NodeId, Priority>::num_nodes() const { 158 return all_nodes_.size(); 159 } 160 161 template <typename NodeId, typename Priority> 162 bool SpdyPriorityForest<NodeId, Priority>::NodeExists(NodeId node_id) const { 163 return all_nodes_.count(node_id) != 0; 164 } 165 166 template <typename NodeId, typename Priority> 167 bool SpdyPriorityForest<NodeId, Priority>::AddRootNode( 168 NodeId node_id, Priority priority) { 169 if (NodeExists(node_id)) { 170 return false; 171 } 172 Node* new_node = &all_nodes_[node_id]; 173 new_node->type = ROOT_NODE; 174 new_node->depends_on.priority = priority; 175 return true; 176 } 177 178 template <typename NodeId, typename Priority> 179 bool SpdyPriorityForest<NodeId, Priority>::AddNonRootNode( 180 NodeId node_id, NodeId parent_id, bool unordered) { 181 if (NodeExists(node_id) || !NodeExists(parent_id)) { 182 return false; 183 } 184 185 Node* parent = &all_nodes_[parent_id]; 186 if (parent->child != NodeId()) { 187 return false; 188 } 189 190 Node* new_node = &all_nodes_[node_id]; 191 new_node->type = (unordered ? NONROOT_UNORDERED : NONROOT_ORDERED); 192 new_node->depends_on.parent_id = parent_id; 193 parent->child = node_id; 194 return true; 195 } 196 197 template <typename NodeId, typename Priority> 198 bool SpdyPriorityForest<NodeId, Priority>::RemoveNode(NodeId node_id) { 199 if (!NodeExists(node_id)) { 200 return false; 201 } 202 const Node& node = all_nodes_[node_id]; 203 204 // If the node to be removed is not a root node, we need to change its 205 // parent's child ID. 206 if (node.type != ROOT_NODE) { 207 DCHECK(NodeExists(node.depends_on.parent_id)); 208 Node* parent = &all_nodes_[node.depends_on.parent_id]; 209 DCHECK_EQ(node_id, parent->child); 210 parent->child = node.child; 211 } 212 213 // If the node has a child, we need to change the child's priority or parent. 214 if (node.child != NodeId()) { 215 DCHECK(NodeExists(node.child)); 216 Node* child = &all_nodes_[node.child]; 217 DCHECK_NE(ROOT_NODE, child->type); 218 DCHECK_EQ(node_id, child->depends_on.parent_id); 219 // Make the child's new depends_on be the node's depends_on (whether that 220 // be a priority or a parent node ID). 221 child->depends_on = node.depends_on; 222 // If the removed node was a root, its child is now a root. Otherwise, the 223 // child will be be unordered if and only if it was already unordered and 224 // the removed not is also not ordered. 225 if (node.type == ROOT_NODE) { 226 child->type = ROOT_NODE; 227 } else if (node.type == NONROOT_ORDERED) { 228 child->type = NONROOT_ORDERED; 229 } 230 } 231 232 // Delete the node. 233 all_nodes_.erase(node_id); 234 return true; 235 } 236 237 template <typename NodeId, typename Priority> 238 Priority SpdyPriorityForest<NodeId, Priority>::GetPriority( 239 NodeId node_id) const { 240 const Node* node = FindNode(node_id); 241 if (node != NULL && node->type == ROOT_NODE) { 242 return node->depends_on.priority; 243 } else { 244 return Priority(); 245 } 246 } 247 248 template <typename NodeId, typename Priority> 249 NodeId SpdyPriorityForest<NodeId, Priority>::GetParent(NodeId node_id) const { 250 const Node* node = FindNode(node_id); 251 if (node != NULL && node->type != ROOT_NODE) { 252 return node->depends_on.parent_id; 253 } else { 254 return NodeId(); 255 } 256 } 257 258 template <typename NodeId, typename Priority> 259 bool SpdyPriorityForest<NodeId, Priority>::IsNodeUnordered( 260 NodeId node_id) const { 261 const Node* node = FindNode(node_id); 262 return node != NULL && node->type == NONROOT_UNORDERED; 263 } 264 265 template <typename NodeId, typename Priority> 266 NodeId SpdyPriorityForest<NodeId, Priority>::GetChild(NodeId node_id) const { 267 const Node* node = FindNode(node_id); 268 if (node != NULL) { 269 return node->child; 270 } else { 271 return NodeId(); 272 } 273 } 274 275 template <typename NodeId, typename Priority> 276 bool SpdyPriorityForest<NodeId, Priority>::SetPriority( 277 NodeId node_id, Priority priority) { 278 if (!NodeExists(node_id)) { 279 return false; 280 } 281 282 Node* node = &all_nodes_[node_id]; 283 // If this is not already a root node, we need to make it be a root node. 284 if (node->type != ROOT_NODE) { 285 DCHECK(NodeExists(node->depends_on.parent_id)); 286 Node* parent = &all_nodes_[node->depends_on.parent_id]; 287 parent->child = NodeId(); 288 node->type = ROOT_NODE; 289 } 290 291 node->depends_on.priority = priority; 292 return true; 293 } 294 295 template <typename NodeId, typename Priority> 296 bool SpdyPriorityForest<NodeId, Priority>::SetParent( 297 NodeId node_id, NodeId parent_id, bool unordered) { 298 if (!NodeExists(node_id) || !NodeExists(parent_id)) { 299 return false; 300 } 301 302 Node* node = &all_nodes_[node_id]; 303 Node* new_parent = &all_nodes_[parent_id]; 304 // If the new parent is already the node's parent, all we have to do is 305 // update the node type and we're done. 306 if (new_parent->child == node_id) { 307 node->type = (unordered ? NONROOT_UNORDERED : NONROOT_ORDERED); 308 return true; 309 } 310 // Otherwise, if the new parent already has a child, we fail. 311 if (new_parent->child != NodeId()) { 312 return false; 313 } 314 315 // Next, make sure we won't create a cycle. 316 if (node_id == parent_id) return false; 317 Node* last = node; 318 NodeId last_id = node_id; 319 while (last->child != NodeId()) { 320 if (last->child == parent_id) return false; 321 last_id = last->child; 322 DCHECK(NodeExists(last_id)); 323 last = &all_nodes_[last_id]; 324 } 325 326 // If the node is not a root, we need clear its old parent's child field 327 // (unless the old parent is the same as the new parent). 328 if (node->type != ROOT_NODE) { 329 const NodeId old_parent_id = node->depends_on.parent_id; 330 DCHECK(NodeExists(old_parent_id)); 331 DCHECK(old_parent_id != parent_id); 332 Node* old_parent = &all_nodes_[old_parent_id]; 333 DCHECK_EQ(node_id, old_parent->child); 334 old_parent->child = NodeId(); 335 } 336 337 // Make the change. 338 node->type = (unordered ? NONROOT_UNORDERED : NONROOT_ORDERED); 339 node->depends_on.parent_id = parent_id; 340 new_parent->child = node_id; 341 return true; 342 } 343 344 template <typename NodeId, typename Priority> 345 bool SpdyPriorityForest<NodeId, Priority>::IsMarkedReadyToRead( 346 NodeId node_id) const { 347 return IsMarked(node_id, kReadyToRead); 348 } 349 350 template <typename NodeId, typename Priority> 351 bool SpdyPriorityForest<NodeId, Priority>::MarkReadyToRead(NodeId node_id) { 352 return Mark(node_id, kReadyToRead); 353 } 354 355 template <typename NodeId, typename Priority> 356 bool SpdyPriorityForest<NodeId, Priority>::MarkNoLongerReadyToRead( 357 NodeId node_id) { 358 return Unmark(node_id, kReadyToRead); 359 } 360 361 template <typename NodeId, typename Priority> 362 NodeId SpdyPriorityForest<NodeId, Priority>::NextNodeToRead() { 363 return FirstMarkedNode(kReadyToRead); 364 } 365 366 template <typename NodeId, typename Priority> 367 bool SpdyPriorityForest<NodeId, Priority>::IsMarkedReadyToWrite( 368 NodeId node_id) const { 369 return IsMarked(node_id, kReadyToWrite); 370 } 371 372 template <typename NodeId, typename Priority> 373 bool SpdyPriorityForest<NodeId, Priority>::MarkReadyToWrite(NodeId node_id) { 374 return Mark(node_id, kReadyToWrite); 375 } 376 377 template <typename NodeId, typename Priority> 378 bool SpdyPriorityForest<NodeId, Priority>::MarkNoLongerReadyToWrite( 379 NodeId node_id) { 380 return Unmark(node_id, kReadyToWrite); 381 } 382 383 template <typename NodeId, typename Priority> 384 NodeId SpdyPriorityForest<NodeId, Priority>::NextNodeToWrite() { 385 return FirstMarkedNode(kReadyToWrite); 386 } 387 388 template <typename NodeId, typename Priority> 389 bool SpdyPriorityForest<NodeId, Priority>::IsMarked( 390 NodeId node_id, unsigned int flag) const { 391 const Node* node = FindNode(node_id); 392 return node != NULL && (node->flags & flag) != 0; 393 } 394 395 template <typename NodeId, typename Priority> 396 bool SpdyPriorityForest<NodeId, Priority>::Mark( 397 NodeId node_id, unsigned int flag) { 398 if (!NodeExists(node_id)) { 399 return false; 400 } 401 all_nodes_[node_id].flags |= flag; 402 return true; 403 } 404 405 template <typename NodeId, typename Priority> 406 bool SpdyPriorityForest<NodeId, Priority>::Unmark( 407 NodeId node_id, unsigned int flag) { 408 if (!NodeExists(node_id)) { 409 return false; 410 } 411 all_nodes_[node_id].flags &= ~flag; 412 return true; 413 } 414 415 template <typename NodeId, typename Priority> 416 NodeId SpdyPriorityForest<NodeId, Priority>::FirstMarkedNode( 417 unsigned int flag) { 418 // TODO(mdsteele): This is an *incredibly* stupid brute force solution. 419 420 // Get all root nodes that have at least one marked child. 421 uint64 total_weight = 0; 422 std::map<uint64, NodeId> roots; // maps cumulative weight to root node ID 423 for (typename NodeMap::const_iterator iter = all_nodes_.begin(); 424 iter != all_nodes_.end(); ++iter) { 425 const NodeId root_id = iter->first; 426 const Node& root = iter->second; 427 if (root.type == ROOT_NODE) { 428 // See if there is at least one marked node in this root's chain. 429 for (const Node* node = &root; ; node = &all_nodes_[node->child]) { 430 if ((node->flags & flag) != 0) { 431 total_weight += static_cast<uint64>(root.depends_on.priority); 432 roots[total_weight] = root_id; 433 break; 434 } 435 if (node->child == NodeId()) { 436 break; 437 } 438 DCHECK(NodeExists(node->child)); 439 } 440 } 441 } 442 443 // If there are no ready nodes, then return NodeId(). 444 if (total_weight == 0) { 445 DCHECK(roots.empty()); 446 return NodeId(); 447 } else { 448 DCHECK(!roots.empty()); 449 } 450 451 // Randomly select a tree to use. 452 typename std::map<uint64, NodeId>::const_iterator root_iter = 453 roots.upper_bound(base::RandGenerator(total_weight)); 454 DCHECK(root_iter != roots.end()); 455 const NodeId root_id = root_iter->second; 456 457 // Find the first node in the chain that is ready. 458 NodeId node_id = root_id; 459 while (true) { 460 DCHECK(NodeExists(node_id)); 461 Node* node = &all_nodes_[node_id]; 462 if ((node->flags & flag) != 0) { 463 // There might be more nodes that are ready and that are linked to this 464 // one in an unordered chain. Find all of them, then pick one randomly. 465 std::vector<NodeId> group; 466 group.push_back(node_id); 467 for (Node* next = node; next->child != NodeId();) { 468 DCHECK(NodeExists(next->child)); 469 Node *child = &all_nodes_[next->child]; 470 DCHECK_NE(ROOT_NODE, child->type); 471 if (child->type != NONROOT_UNORDERED) { 472 break; 473 } 474 if ((child->flags & flag) != 0) { 475 group.push_back(next->child); 476 } 477 next = child; 478 } 479 return group[base::RandGenerator(group.size())]; 480 } 481 node_id = node->child; 482 } 483 } 484 485 template <typename NodeId, typename Priority> 486 const typename SpdyPriorityForest<NodeId, Priority>::Node* 487 SpdyPriorityForest<NodeId, Priority>::FindNode(NodeId node_id) const { 488 typename NodeMap::const_iterator iter = all_nodes_.find(node_id); 489 if (iter == all_nodes_.end()) { 490 return NULL; 491 } 492 return &iter->second; 493 } 494 495 template <typename NodeId, typename Priority> 496 bool SpdyPriorityForest<NodeId, Priority>::ValidateInvariantsForTests() const { 497 for (typename NodeMap::const_iterator iter = all_nodes_.begin(); 498 iter != all_nodes_.end(); ++iter) { 499 const NodeId node_id = iter->first; 500 const Node& node = iter->second; 501 if (node.type != ROOT_NODE && 502 (!NodeExists(node.depends_on.parent_id) || 503 GetChild(node.depends_on.parent_id) != node_id)) { 504 return false; 505 } 506 if (node.child != NodeId()) { 507 if (!NodeExists(node.child) || node_id != GetParent(node.child)) { 508 return false; 509 } 510 } 511 512 NodeId child_id = node.child; 513 int count = 0; 514 while (child_id != NodeId()) { 515 if (count > num_nodes() || node_id == child_id) { 516 return false; 517 } 518 child_id = GetChild(child_id); 519 ++count; 520 } 521 } 522 return true; 523 } 524 525 } // namespace net 526 527 #endif // NET_SPDY_SPDY_PRIORITY_FOREST_H_ 528