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 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
  35 namespace test {
  36 template <typename NodeId>
  37 class SpdyPriorityTreePeer;
  38 }
  39
  40 const int kRootNodeId = 0;
  41 const int kDefaultWeight = 16;
  42 const int kMinWeight = 1;
  43 const int kMaxWeight = 256;
  44
  45 template <typename NodeId>
  46 class 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
 158 template <typename NodeId>
 159 SpdyPriorityTree<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
 169 template <typename NodeId>
 170 SpdyPriorityTree<NodeId>::~SpdyPriorityTree() {}
 171
 172 template <typename NodeId>
 173 SpdyPriorityTree<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
 184 template <typename NodeId>
 185 SpdyPriorityTree<NodeId>::Node::~Node() {
 186   delete child_list;
 187 }
 188
 189 template <typename NodeId>
 190 bool 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
 196 template <typename NodeId>
 197 int SpdyPriorityTree<NodeId>::num_nodes() const {
 198   return all_nodes_.size();
 199 }
 200
 201 template <typename NodeId>
 202 bool SpdyPriorityTree<NodeId>::NodeExists(NodeId node_id) const {
 203   return all_nodes_.count(node_id) != 0;
 204 }
 205
 206 template <typename NodeId>
 207 bool 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
 244 template <typename NodeId>
 245 bool 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
 283 template <typename NodeId>
 284 int 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
 292 template <typename NodeId>
 293 NodeId 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
 301 template <typename NodeId>
 302 std::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
 310 template <typename NodeId>
 311 bool 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
 330 template <typename NodeId>
 331 bool 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
 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 void 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
 417 template <typename NodeId>
 418 const typename SpdyPriorityTree<NodeId>::Node*
 419 SpdyPriorityTree<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
 427 template <typename NodeId>
 428 bool 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
 437 template <typename NodeId>
 438 std::vector<std::pair<NodeId, float> >
 439 SpdyPriorityTree<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
 497 template <typename NodeId>
 498 bool 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_