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#ifndef NET_SPDY_SPDY_PRIORITY_TREE_H_ 6#define NET_SPDY_SPDY_PRIORITY_TREE_H_ 7 8#include <cmath> 9#include <list> 10#include <map> 11#include <queue> 12#include <set> 13 14#include "base/basictypes.h" 15#include "base/containers/hash_tables.h" 16#include "base/logging.h" 17#include "base/memory/scoped_ptr.h" 18 19namespace net { 20 21// This data structure implements the HTTP2 prioritization data structure 22// defined in draft standard: 23// http://tools.ietf.org/html/draft-ietf-httpbis-http2-13 24// 25// Nodes can be added and removed, and dependencies between them defined. Each 26// node can have at most one parent and at most one child (forming a list), but 27// there can be multiple lists, with each list root having its own priority. 28// Individual nodes can also be marked as ready to read/write, and then the 29// whole structure can be queried to pick the next node to read/write out of 30// those ready. 31// 32// The NodeId type must be a POD that supports comparison (most 33// likely, it will be a number). 34 35namespace test { 36template <typename NodeId> 37class SpdyPriorityTreePeer; 38} 39 40const int kRootNodeId = 0; 41const int kDefaultWeight = 16; 42const int kMinWeight = 1; 43const int kMaxWeight = 256; 44 45template <typename NodeId> 46class SpdyPriorityTree { 47 typedef std::vector<std::pair<NodeId, float> > PriorityNodeList; 48 49 public: 50 SpdyPriorityTree(); 51 ~SpdyPriorityTree(); 52 53 typedef std::list<NodeId> List; 54 struct Node { 55 Node(); 56 ~Node(); 57 58 NodeId id; 59 NodeId parent_id; 60 int weight; // Weights can range between 1 and 256 (inclusive). 61 // The total weight of this node's direct descendants. 62 int total_child_weights; 63 // The total weight of direct descendants that are writeable 64 // (ready to write and not blocked). This value does not necessarily 65 // reflect the current state of the tree; instead, we lazily update it 66 // on calls to PropagateNodeState(node.id). 67 int total_writeable_child_weights; 68 List* child_list; // node ID's of children, if any 69 bool blocked; // Is the associated stream write-blocked? 70 bool ready; // Does the stream have data ready for writing? 71 float priority; // The fraction of resources to dedicate to this node. 72 }; 73 74 // Orders in descending order of priority. 75 struct NodePriorityComparator { 76 bool operator ()(const std::pair<NodeId, float>& lhs, 77 const std::pair<NodeId, float>& rhs); 78 }; 79 80 friend class test::SpdyPriorityTreePeer<NodeId>; 81 82 // Return the number of nodes currently in the tree. 83 int num_nodes() const; 84 85 // Return true if the tree contains a node with the given ID. 86 bool NodeExists(NodeId node_id) const; 87 88 // Add a new node with the given weight and parent. Non-exclusive nodes 89 // simply get added below the parent node. If exclusive = true, the node 90 // becomes the parent's sole child and the parent's previous children 91 // become the children of the new node. 92 // Returns true on success. Returns false if the node already exists 93 // in the tree, or if the parent node does not exist. 94 bool AddNode(NodeId node_id, NodeId parent_id, int weight, bool exclusive); 95 96 // Remove an existing node from the tree. Returns true on success, or 97 // false if the node doesn't exist. 98 bool RemoveNode(NodeId node_id); 99 100 // Get the weight of the given node. 101 int GetWeight(NodeId node_id) const; 102 103 // Get the parent of the given node. If the node doesn't exist, or is a root 104 // node (and thus has no parent), returns NodeId(). 105 NodeId GetParent(NodeId node_id) const; 106 107 // Get the child list of the given node. If the node doesn't exist, or has no 108 // child, returns NULL. 109 std::list<NodeId>* GetChildren(NodeId node_id) const; 110 111 // Set the priority of the given node. 112 bool SetWeight(NodeId node_id, int weight); 113 114 // Set the parent of the given node. Returns true on success. 115 // Returns false and has no effect if the node and/or the parent doesn't 116 // exist. If the new parent is a descendant of the node (i.e. this would have 117 // created a cycle) then we rearrange the topology of the tree as described 118 // in the HTTP2 spec. 119 bool SetParent(NodeId node_id, NodeId parent_id, bool exclusive); 120 121 // Returns true if the node parent_id has child_id in its child_list. 122 bool HasChild(NodeId parent_id, NodeId child_id) const; 123 124 // Mark a node as blocked or unblocked. Return true on success, or false 125 // if unable to mark the specified node. 126 bool SetBlocked(NodeId node_id, bool blocked); 127 128 // Mark whether or not a node is ready to write; i.e. whether there is 129 // buffered data for the associated stream. Return true on success, or false 130 // if unable to mark the specified node. 131 bool SetReady(NodeId node_id, bool ready); 132 133 // Return true if all internal invariants hold (useful for unit tests). 134 // Unless there are bugs, this should always return true. 135 bool ValidateInvariantsForTests() const; 136 137 // Get the given node, or return NULL if it doesn't exist. 138 const Node* FindNode(NodeId node_id) const; 139 140 // Returns an ordered list of writeable nodes and their priorities. 141 // Priority is calculated as: 142 // parent's priority * (node's weight / sum of sibling weights) 143 PriorityNodeList GetPriorityList(); 144 145 protected: 146 // Update the value of total_writeable_child_weights for the given node 147 // to reflect the current state of the tree. 148 void PropagateNodeState(NodeId node); 149 150 private: 151 typedef base::hash_map<NodeId, Node> NodeMap; 152 153 NodeMap all_nodes_; // maps from node IDs to Node objects 154 155 DISALLOW_COPY_AND_ASSIGN(SpdyPriorityTree); 156}; 157 158template <typename NodeId> 159SpdyPriorityTree<NodeId>::SpdyPriorityTree() { 160 Node* root_node = &all_nodes_[kRootNodeId]; 161 root_node->id = kRootNodeId; 162 root_node->weight = kDefaultWeight; 163 root_node->parent_id = static_cast<NodeId>(kRootNodeId); 164 root_node->child_list = new std::list<NodeId>; 165 root_node->priority = 1.0; 166 root_node->ready = true; 167} 168 169template <typename NodeId> 170SpdyPriorityTree<NodeId>::~SpdyPriorityTree() {} 171 172template <typename NodeId> 173SpdyPriorityTree<NodeId>::Node::Node() : 174 parent_id(kRootNodeId), 175 weight(kDefaultWeight), 176 total_child_weights(0), 177 total_writeable_child_weights(0), 178 child_list(), 179 blocked(false), 180 ready(false), 181 priority(0) { 182} 183 184template <typename NodeId> 185SpdyPriorityTree<NodeId>::Node::~Node() { 186 delete child_list; 187} 188 189template <typename NodeId> 190bool SpdyPriorityTree<NodeId>::NodePriorityComparator::operator ()( 191 const std::pair<NodeId, float>& lhs, 192 const std::pair<NodeId, float>& rhs) { 193 return lhs.second > rhs.second; 194} 195 196template <typename NodeId> 197int SpdyPriorityTree<NodeId>::num_nodes() const { 198 return all_nodes_.size(); 199} 200 201template <typename NodeId> 202bool SpdyPriorityTree<NodeId>::NodeExists(NodeId node_id) const { 203 return all_nodes_.count(node_id) != 0; 204} 205 206template <typename NodeId> 207bool SpdyPriorityTree<NodeId>::AddNode(NodeId node_id, 208 NodeId parent_id, 209 int weight, 210 bool exclusive) { 211 if (NodeExists(node_id) || !NodeExists(parent_id)) { 212 return false; 213 } 214 if (weight < kMinWeight || weight > kMaxWeight) { 215 return false; 216 } 217 Node* parent = &all_nodes_[parent_id]; 218 Node* new_node = &all_nodes_[node_id]; 219 new_node->id = node_id; 220 new_node->weight = weight; 221 new_node->parent_id = parent_id; 222 if (exclusive) { 223 // Move the parent's current children below the new node. 224 new_node->child_list = parent->child_list; 225 new_node->total_child_weights = parent->total_child_weights; 226 // Update each child's parent_id. 227 for (typename List::iterator it = new_node->child_list->begin(); 228 it != new_node->child_list->end(); ++it) { 229 Node* child = &all_nodes_[*it]; 230 child->parent_id = node_id; 231 } 232 // Clear parent's old child data. 233 parent->child_list = new std::list<NodeId>; 234 parent->total_child_weights = 0; 235 } else { 236 new_node->child_list = new std::list<NodeId>; 237 } 238 // Add new node to parent. 239 parent->child_list->push_back(node_id); 240 parent->total_child_weights += weight; 241 return true; 242} 243 244template <typename NodeId> 245bool SpdyPriorityTree<NodeId>::RemoveNode(NodeId node_id) { 246 if (node_id == static_cast<NodeId>(kRootNodeId) || !NodeExists(node_id)) { 247 return false; 248 } 249 const Node& node = all_nodes_[node_id]; 250 251 DCHECK(NodeExists(node.parent_id)); 252 Node* parent = &all_nodes_[node.parent_id]; 253 // Remove the node id from parent's child list. 254 parent->child_list->remove(node_id); 255 parent->total_child_weights -= node.weight; 256 257 // Move the node's children to the parent's child list. 258 if (node.child_list != NULL) { 259 // Update each child's parent_id and weight. 260 for (typename List::iterator it = node.child_list->begin(); 261 it != node.child_list->end(); ++it) { 262 Node* child = &all_nodes_[*it]; 263 child->parent_id = node.parent_id; 264 // Divide the removed node's weight among its children, rounding to the 265 // nearest valid weight. 266 float float_weight = node.weight * static_cast<float>(child->weight) / 267 static_cast<float>(node.total_child_weights); 268 int new_weight = std::floor(float_weight + 0.5); 269 if (new_weight == 0) { 270 new_weight = 1; 271 } 272 child->weight = new_weight; 273 parent->total_child_weights += child->weight; 274 } 275 parent->child_list->splice(parent->child_list->end(), *node.child_list); 276 } 277 278 // Delete the node. 279 all_nodes_.erase(node_id); 280 return true; 281} 282 283template <typename NodeId> 284int SpdyPriorityTree<NodeId>::GetWeight(NodeId node_id) const { 285 const Node* node = FindNode(node_id); 286 if (node != NULL) { 287 return node->weight; 288 } 289 return 0; 290} 291 292template <typename NodeId> 293NodeId SpdyPriorityTree<NodeId>::GetParent(NodeId node_id) const { 294 const Node* node = FindNode(node_id); 295 if (node != NULL && node->id != static_cast<NodeId>(kRootNodeId)) { 296 return node->parent_id; 297 } 298 return static_cast<NodeId>(kRootNodeId); 299} 300 301template <typename NodeId> 302std::list<NodeId>* SpdyPriorityTree<NodeId>::GetChildren(NodeId node_id) const { 303 const Node* node = FindNode(node_id); 304 if (node != NULL) { 305 return node->child_list; 306 } 307 return NULL; 308} 309 310template <typename NodeId> 311bool SpdyPriorityTree<NodeId>::SetWeight( 312 NodeId node_id, int weight) { 313 if (!NodeExists(node_id)) { 314 return false; 315 } 316 if (weight < kMinWeight || weight > kMaxWeight) { 317 return false; 318 } 319 320 Node* node = &all_nodes_[node_id]; 321 Node* parent = &all_nodes_[node->parent_id]; 322 323 parent->total_child_weights += (weight - node->weight); 324 node->weight = weight; 325 326 return true; 327} 328 329 330template <typename NodeId> 331bool SpdyPriorityTree<NodeId>::SetParent( 332 NodeId node_id, NodeId parent_id, bool exclusive) { 333 if (!NodeExists(node_id) || !NodeExists(parent_id)) { 334 return false; 335 } 336 if (node_id == parent_id) return false; 337 338 Node* node = &all_nodes_[node_id]; 339 Node* new_parent = &all_nodes_[parent_id]; 340 // If the new parent is already the node's parent, we're done. 341 if (node->parent_id == parent_id) { 342 return true; 343 } 344 345 // Next, check to see if the new parent is currently a descendant 346 // of the node. 347 Node* last = new_parent; 348 NodeId last_id = parent_id; 349 bool cycle_exists = false; 350 while (last->parent_id != static_cast<NodeId>(kRootNodeId)) { 351 if (last->parent_id == node_id) { 352 cycle_exists = true; 353 break; 354 } 355 last_id = last->parent_id; 356 DCHECK(NodeExists(last_id)); 357 last = &all_nodes_[last_id]; 358 } 359 360 if (cycle_exists) { 361 // The new parent moves to the level of the current node. 362 SetParent(parent_id, node->parent_id, false); 363 } 364 365 // Remove node from old parent's child list. 366 const NodeId old_parent_id = node->parent_id; 367 DCHECK(NodeExists(old_parent_id)); 368 Node* old_parent = &all_nodes_[old_parent_id]; 369 old_parent->child_list->remove(node_id); 370 old_parent->total_child_weights -= node->weight; 371 372 // Make the change. 373 node->parent_id = parent_id; 374 new_parent->child_list->push_back(node_id); 375 new_parent->total_child_weights += node->weight; 376 return true; 377} 378 379template <typename NodeId> 380bool SpdyPriorityTree<NodeId>::SetBlocked(NodeId node_id, bool blocked) { 381 if (!NodeExists(node_id)) { 382 return false; 383 } 384 385 Node* node = &all_nodes_[node_id]; 386 node->blocked = blocked; 387 return true; 388} 389 390template <typename NodeId> 391bool SpdyPriorityTree<NodeId>::SetReady(NodeId node_id, bool ready) { 392 if (!NodeExists(node_id)) { 393 return false; 394 } 395 Node* node = &all_nodes_[node_id]; 396 node->ready = ready; 397 return true; 398} 399 400template <typename NodeId> 401void SpdyPriorityTree<NodeId>::PropagateNodeState(NodeId node_id) { 402 // Reset total_writeable_child_weights to its maximum value. 403 Node* node = &all_nodes_[node_id]; 404 node->total_writeable_child_weights = node->total_child_weights; 405 for (typename List::iterator it = node->child_list->begin(); 406 it != node->child_list->end(); ++it) { 407 PropagateNodeState(*it); 408 } 409 if (node->total_writeable_child_weights == 0 && 410 (node->blocked || !node->ready)) { 411 // Tell the parent that this entire subtree is unwriteable. 412 Node* parent = &all_nodes_[node->parent_id]; 413 parent->total_writeable_child_weights -= node->weight; 414 } 415} 416 417template <typename NodeId> 418const typename SpdyPriorityTree<NodeId>::Node* 419SpdyPriorityTree<NodeId>::FindNode(NodeId node_id) const { 420 typename NodeMap::const_iterator iter = all_nodes_.find(node_id); 421 if (iter == all_nodes_.end()) { 422 return NULL; 423 } 424 return &iter->second; 425} 426 427template <typename NodeId> 428bool SpdyPriorityTree<NodeId>::HasChild(NodeId parent_id, 429 NodeId child_id) const { 430 const Node* parent = FindNode(parent_id); 431 return parent->child_list->end() != 432 std::find(parent->child_list->begin(), 433 parent->child_list->end(), 434 child_id); 435} 436 437template <typename NodeId> 438std::vector<std::pair<NodeId, float> > 439SpdyPriorityTree<NodeId>::GetPriorityList() { 440 typedef std::pair<NodeId, float> PriorityNode; 441 typedef std::vector<PriorityNode> PriorityList; 442 PriorityList priority_list; 443 444 // Update total_writeable_child_weights to reflect the current 445 // state of the tree. 446 PropagateNodeState(kRootNodeId); 447 448 List queue; 449 const Node* root_node = FindNode(kRootNodeId); 450 DCHECK(root_node->priority == 1.0); 451 // Start by examining our top-level nodes. 452 for (typename List::iterator it = root_node->child_list->begin(); 453 it != root_node->child_list->end(); ++it) { 454 queue.push_back(*it); 455 } 456 while (!queue.empty()) { 457 NodeId current_node_id = queue.front(); 458 Node* current_node = &all_nodes_[current_node_id]; 459 const Node* parent_node = FindNode(current_node->parent_id); 460 if (current_node->blocked || !current_node->ready) { 461 if (current_node->total_writeable_child_weights > 0) { 462 // This node isn't writeable, but it has writeable children. 463 // Calculate the total fraction of resources we can allot 464 // to this subtree. 465 current_node->priority = parent_node->priority * 466 (static_cast<float>(current_node->weight) / 467 static_cast<float>(parent_node->total_writeable_child_weights)); 468 // Examine the children. 469 for (typename List::iterator it = current_node->child_list->begin(); 470 it != current_node->child_list->end(); ++it) { 471 queue.push_back(*it); 472 } 473 } else { 474 // There's nothing to see in this subtree. 475 current_node->priority = 0; 476 } 477 } else { 478 // This node is writeable; calculate its priority. 479 current_node->priority = parent_node->priority * 480 (static_cast<float>(current_node->weight) / 481 static_cast<float>(parent_node->total_writeable_child_weights)); 482 // Add this node to the priority list. 483 priority_list.push_back(PriorityNode(current_node_id, 484 current_node->priority)); 485 } 486 // Remove this node from the queue. 487 queue.pop_front(); 488 } 489 490 // Sort the nodes in descending order of priority. 491 std::sort(priority_list.begin(), priority_list.end(), 492 NodePriorityComparator()); 493 494 return priority_list; 495} 496 497template <typename NodeId> 498bool SpdyPriorityTree<NodeId>::ValidateInvariantsForTests() const { 499 int total_nodes = 0; 500 int nodes_visited = 0; 501 // Iterate through all nodes in the map. 502 for (typename NodeMap::const_iterator iter = all_nodes_.begin(); 503 iter != all_nodes_.end(); ++iter) { 504 ++total_nodes; 505 ++nodes_visited; 506 const Node& node = iter->second; 507 // All nodes except the root should have a parent, and should appear in 508 // the child_list of that parent. 509 if (node.id != static_cast<NodeId>(kRootNodeId) && 510 (!NodeExists(node.parent_id) || 511 !HasChild(node.parent_id, node.id))) { 512 DLOG(INFO) << "Parent node " << node.parent_id 513 << " does not exist, or does not list node " << node.id 514 << " as its child."; 515 return false; 516 } 517 518 if (!node.child_list->empty()) { 519 int total_child_weights = 0; 520 // Iterate through the node's children. 521 for (typename List::iterator it = node.child_list->begin(); 522 it != node.child_list->end(); ++it) { 523 ++nodes_visited; 524 // Each node in the list should exist and should have this node 525 // set as its parent. 526 if (!NodeExists(*it) || node.id != GetParent(*it)) { 527 DLOG(INFO) << "Child node " << *it << " does not exist, " 528 << "or does not list " << node.id << " as its parent."; 529 return false; 530 } 531 const Node* child = FindNode(*it); 532 total_child_weights += child->weight; 533 } 534 // Verify that total_child_weights is correct. 535 if (total_child_weights != node.total_child_weights) { 536 DLOG(INFO) << "Child weight totals do not agree. For node " << node.id 537 << " total_child_weights has value " 538 << node.total_child_weights 539 << ", expected " << total_child_weights; 540 return false; 541 } 542 } 543 } 544 545 // Make sure num_nodes reflects the total number of nodes the map contains. 546 if (total_nodes != num_nodes()) { 547 DLOG(INFO) << "Map contains incorrect number of nodes."; 548 return false; 549 } 550 // Validate the validation function; we should have visited each node twice 551 // (except for the root) 552 DCHECK(nodes_visited == 2*num_nodes() - 1); 553 return true; 554} 555 556} // namespace net 557 558#endif // NET_SPDY_SPDY_PRIORITY_TREE_H_ 559