net/spdy/spdy_priority_tree.h

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