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