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