net/spdy/spdy_priority_forest.h

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