path: root/net/spdy/http2_write_scheduler.h

// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef NET_SPDY_HTTP2_WRITE_SCHEDULER_H_
#define NET_SPDY_HTTP2_WRITE_SCHEDULER_H_

#include <stdint.h>

#include <algorithm>
#include <cmath>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>

#include "base/containers/hash_tables.h"
#include "base/containers/linked_list.h"
#include "base/logging.h"
#include "base/macros.h"
#include "base/memory/scoped_ptr.h"
#include "base/stl_util.h"

namespace net {

// This data structure implements the HTTP/2 stream priority tree defined in
// section 5.3 of RFC 7540:
// http://tools.ietf.org/html/rfc7540#section-5.3
//
// Streams can be added and removed, and dependencies between them defined.
// Streams constitute a tree rooted at stream ID 0: each stream has a single
// parent stream, and 0 or more child streams.  Individual streams can be
// marked as ready to read/write, and then the whole structure can be queried
// to pick the next stream to read/write out of those that are ready.
//
// The StreamIdType type must be a POD that supports comparison (most
// likely, it will be a number).

namespace test {
template <typename StreamIdType>
class Http2PriorityWriteSchedulerPeer;
}

const unsigned int kHttp2RootStreamId = 0;
const int kHttp2DefaultStreamWeight = 16;
const int kHttp2MinStreamWeight = 1;
const int kHttp2MaxStreamWeight = 256;

template <typename StreamIdType>
class Http2PriorityWriteScheduler {
 public:
  Http2PriorityWriteScheduler();

  friend class test::Http2PriorityWriteSchedulerPeer<StreamIdType>;

  // Return the number of streams currently in the tree.
  int num_streams() const;

  // Return true if the tree contains a stream with the given ID.
  bool StreamRegistered(StreamIdType stream_id) const;

  // Registers a new stream with the given weight and parent, adding it to the
  // dependency tree. Non-exclusive streams simply get added below the parent
  // stream. If exclusive = true, the stream becomes the parent's sole child
  // and the parent's previous children become the children of the new
  // stream. If the stream was already registered, logs DFATAL and does
  // nothing. If the parent stream is not registered, logs DFATAL and uses the
  // root stream as the parent.
  void RegisterStream(StreamIdType stream_id,
                      StreamIdType parent_id,
                      int weight,
                      bool exclusive);

  // Unregisters the given stream from the scheduler, removing it from the
  // dependency tree. If the stream was not previously registered, logs DFATAL
  // and does nothing.
  void UnregisterStream(StreamIdType stream_id);

  // Returns the weight value for the specified stream. If the stream is not
  // registered, logs DFATAL and returns the lowest weight.
  int GetStreamWeight(StreamIdType stream_id) const;

  // Returns the stream ID for the parent of the given stream. If the stream
  // isn't registered, logs DFATAL and returns the root stream ID (0).
  StreamIdType GetStreamParent(StreamIdType stream_id) const;

  // Returns stream IDs of the children of the given stream, if any. If the
  // stream isn't registered, logs DFATAL and returns an empty vector.
  std::vector<StreamIdType> GetStreamChildren(StreamIdType stream_id) const;

  // Sets the weight of the given stream. If the stream isn't registered or is
  // the root stream, logs DFATAL and does nothing.
  void SetStreamWeight(StreamIdType stream_id, int weight);

  // Sets the parent of the given stream. If the stream and/or parent aren't
  // registered, logs DFATAL and does nothing. If the new parent is a
  // descendant of the stream (i.e. this would have created a cycle) then the
  // topology of the tree is rearranged as described in section 5.3.3 of RFC
  // 7540: https://tools.ietf.org/html/rfc7540#section-5.3.3
  void SetStreamParent(StreamIdType stream_id,
                       StreamIdType parent_id,
                       bool exclusive);

  // Returns true if the stream parent_id has child_id in its children. If
  // either parent or child stream aren't registered, logs DFATAL and returns
  // false.
  bool StreamHasChild(StreamIdType parent_id, StreamIdType child_id) const;

  // Marks the stream as blocked or unblocked. If the stream is not registered,
  // logs DFATAL and does nothing.
  void MarkStreamBlocked(StreamIdType stream_id, bool blocked);

  // Marks the stream as ready or not ready to write; i.e. whether there is
  // buffered data for the associated stream. If the stream is not registered,
  // logs DFATAL and does nothing.
  void MarkStreamReady(StreamIdType stream_id, bool ready);

  // Returns true iff the scheduler has one or more usable streams. A stream is
  // usable if it has ready == true and blocked == false, and is not the direct
  // or indirect child of another stream that itself has ready == true and
  // blocked == false. (Note that the root stream always has ready == false.)
  bool HasUsableStreams() const;

  // If the scheduler has any usable streams, returns the ID of the next usable
  // stream, in the process changing its ready state to false. If the scheduler
  // does not have any usable streams, logs DFATAL and returns the root stream
  // ID (0). If there are multiple usable streams, precedence is given to the
  // one with the highest priority (thus preserving SPDY priority semantics),
  // or, if there are multiple with the highest priority, the one with the
  // lowest ordinal (ensuring round-robin ordering).
  StreamIdType PopNextUsableStream();

 private:
  struct StreamInfo;
  using StreamInfoVector = std::vector<StreamInfo*>;
  using StreamInfoMap = std::unordered_map<StreamIdType, StreamInfo*>;

  struct StreamInfo : public base::LinkNode<StreamInfo> {
    // ID for this stream.
    StreamIdType id;
    // ID of parent stream.
    StreamInfo* parent = nullptr;
    // Weights can range between 1 and 256 (inclusive).
    int weight = kHttp2DefaultStreamWeight;
    // The total weight of this stream's direct descendants.
    int total_child_weights = 0;
    // Pointers to StreamInfos for children, if any.
    StreamInfoVector children;
    // Is the associated stream write-blocked?
    bool blocked = false;
    // Does the stream have data ready for writing?
    bool ready = false;
    // Whether the stream is currently present in scheduling_queue_.
    bool scheduled = false;
    // The scheduling priority of this stream. Streams with higher priority
    // values are scheduled first.
    float priority = 0;
    // Ordinal value for this stream, used to ensure round-robin scheduling:
    // among streams with the same scheduling priority, streams with lower
    // ordinal are scheduled first. The ordinal is reset to a new, greater
    // value when the stream is next inserted into scheduling_queue_.
    int64_t ordinal = 0;

    // Whether the stream ought to be in scheduling_queue_.
    bool IsSchedulable() const { return ready && !blocked; }

    // Whether this stream should be scheduled ahead of another stream.
    bool SchedulesBefore(const StreamInfo& other) const {
      return (priority != other.priority) ? priority > other.priority
                                          : ordinal < other.ordinal;
    }
  };

  static bool Remove(StreamInfoVector* stream_infos,
                     const StreamInfo* stream_info);

  // Clamps weight to a value in [kHttp2MinStreamWeight,
  // kHttp2MaxStreamWeight].
  static int ClampWeight(int weight);

  // Returns true iff any direct or transitive parent of the given stream is
  // currently scheduled.
  static bool HasScheduledAncestor(const StreamInfo& stream_info);

  // Returns StreamInfo for the given stream, or nullptr if it isn't
  // registered.
  const StreamInfo* FindStream(StreamIdType stream_id) const;
  StreamInfo* FindStream(StreamIdType stream_id);

  // Update all priority values in the subtree rooted at the given stream, not
  // including the stream itself. If this results in priority value changes for
  // scheduled streams, those streams are rescheduled to ensure proper ordering
  // of scheduling_queue_.
  void UpdatePrioritiesUnder(StreamInfo* stream_info);

  // Adds or removes stream from scheduling_queue_ according to whether it is
  // schedulable. If stream is newly schedulable, assigns it the next
  // (increasing) ordinal value.
  void UpdateScheduling(StreamInfo* stream_info);

  // Inserts stream into scheduling_queue_ at the appropriate location given
  // its priority and ordinal. Time complexity is O(scheduling_queue.size()).
  void Schedule(StreamInfo* stream_info);

  // Removes stream from scheduling_queue_.
  void Unschedule(StreamInfo* stream_info);

  // Return true if all internal invariants hold (useful for unit tests).
  // Unless there are bugs, this should always return true.
  bool ValidateInvariantsForTests() const;

  // Pointee owned by all_stream_infos_.
  StreamInfo* root_stream_info_;
  // Maps from stream IDs to StreamInfo objects.
  StreamInfoMap all_stream_infos_;
  STLValueDeleter<StreamInfoMap> all_stream_infos_deleter_;
  // Queue containing all streams that are ready and unblocked, ordered with
  // streams of higher priority before streams of lower priority, and, among
  // streams of equal priority, streams with lower ordinal before those with
  // higher ordinal. Note that not all streams in scheduling_queue_ are
  // necessarily usable: some may have ancestor stream(s) that are ready and
  // unblocked. In these situations the occluded child streams are left in the
  // queue, to reduce churn.
  base::LinkedList<StreamInfo> scheduling_queue_;
  // Ordinal value to assign to next node inserted into
  // scheduling_queue_. Incremented after each insertion.
  int64_t next_ordinal_ = 0;

  DISALLOW_COPY_AND_ASSIGN(Http2PriorityWriteScheduler);
};

template <typename StreamIdType>
Http2PriorityWriteScheduler<StreamIdType>::Http2PriorityWriteScheduler()
    : all_stream_infos_deleter_(&all_stream_infos_) {
  root_stream_info_ = new StreamInfo();
  root_stream_info_->id = kHttp2RootStreamId;
  root_stream_info_->weight = kHttp2DefaultStreamWeight;
  root_stream_info_->parent = nullptr;
  root_stream_info_->priority = 1.0;
  root_stream_info_->ready = true;
  all_stream_infos_[kHttp2RootStreamId] = root_stream_info_;
}

template <typename StreamIdType>
int Http2PriorityWriteScheduler<StreamIdType>::num_streams() const {
  return all_stream_infos_.size();
}

template <typename StreamIdType>
bool Http2PriorityWriteScheduler<StreamIdType>::StreamRegistered(
    StreamIdType stream_id) const {
  return ContainsKey(all_stream_infos_, stream_id);
}

template <typename StreamIdType>
void Http2PriorityWriteScheduler<StreamIdType>::RegisterStream(
    StreamIdType stream_id,
    StreamIdType parent_id,
    int weight,
    bool exclusive) {
  if (StreamRegistered(stream_id)) {
    LOG(DFATAL) << "Stream " << stream_id << " already registered";
    return;
  }
  weight = ClampWeight(weight);

  StreamInfo* parent = FindStream(parent_id);
  if (parent == nullptr) {
    LOG(DFATAL) << "Parent stream " << parent_id << " not registered";
    parent = root_stream_info_;
  }

  StreamInfo* new_stream_info = new StreamInfo;
  new_stream_info->id = stream_id;
  new_stream_info->weight = weight;
  new_stream_info->parent = parent;
  all_stream_infos_[stream_id] = new_stream_info;
  if (exclusive) {
    // Move the parent's current children below the new stream.
    using std::swap;
    swap(new_stream_info->children, parent->children);
    new_stream_info->total_child_weights = parent->total_child_weights;
    // Update each child's parent.
    for (StreamInfo* child : new_stream_info->children) {
      child->parent = new_stream_info;
    }
    // Clear parent's old child data.
    DCHECK(parent->children.empty());
    parent->total_child_weights = 0;
  }
  // Add new stream to parent.
  parent->children.push_back(new_stream_info);
  parent->total_child_weights += weight;

  // Update all priorities under parent, since addition of a stream affects
  // sibling priorities as well.
  UpdatePrioritiesUnder(parent);

  // Stream starts with ready == false, so no need to schedule it yet.
  DCHECK(!new_stream_info->IsSchedulable());
}

template <typename StreamIdType>
void Http2PriorityWriteScheduler<StreamIdType>::UnregisterStream(
    StreamIdType stream_id) {
  if (stream_id == kHttp2RootStreamId) {
    LOG(DFATAL) << "Cannot unregister root stream";
    return;
  }
  // Remove the stream from table.
  typename StreamInfoMap::iterator it = all_stream_infos_.find(stream_id);
  if (it == all_stream_infos_.end()) {
    LOG(DFATAL) << "Stream " << stream_id << " not registered";
    return;
  }
  scoped_ptr<StreamInfo> stream_info(std::move(it->second));
  all_stream_infos_.erase(it);
  // If scheduled, unschedule.
  if (stream_info->scheduled) {
    Unschedule(stream_info.get());
  }

  StreamInfo* parent = stream_info->parent;
  // Remove the stream from parent's child list.
  Remove(&parent->children, stream_info.get());
  parent->total_child_weights -= stream_info->weight;

  // Move the stream's children to the parent's child list.
  // Update each child's parent and weight.
  for (StreamInfo* child : stream_info->children) {
    child->parent = parent;
    parent->children.push_back(child);
    // Divide the removed stream's weight among its children, rounding to the
    // nearest valid weight.
    float float_weight = stream_info->weight *
                         static_cast<float>(child->weight) /
                         static_cast<float>(stream_info->total_child_weights);
    int new_weight = floor(float_weight + 0.5);
    if (new_weight == 0) {
      new_weight = 1;
    }
    child->weight = new_weight;
    parent->total_child_weights += child->weight;
  }
  UpdatePrioritiesUnder(parent);
}

template <typename StreamIdType>
int Http2PriorityWriteScheduler<StreamIdType>::GetStreamWeight(
    StreamIdType stream_id) const {
  const StreamInfo* stream_info = FindStream(stream_id);
  if (stream_info == nullptr) {
    LOG(DFATAL) << "Stream " << stream_id << " not registered";
    return kHttp2MinStreamWeight;
  }
  return stream_info->weight;
}

template <typename StreamIdType>
StreamIdType Http2PriorityWriteScheduler<StreamIdType>::GetStreamParent(
    StreamIdType stream_id) const {
  const StreamInfo* stream_info = FindStream(stream_id);
  if (stream_info == nullptr) {
    LOG(DFATAL) << "Stream " << stream_id << " not registered";
    return kHttp2RootStreamId;
  }
  if (stream_info->parent == nullptr) {  // root stream
    return kHttp2RootStreamId;
  }
  return stream_info->parent->id;
}

template <typename StreamIdType>
std::vector<StreamIdType> Http2PriorityWriteScheduler<
    StreamIdType>::GetStreamChildren(StreamIdType stream_id) const {
  std::vector<StreamIdType> child_vec;
  const StreamInfo* stream_info = FindStream(stream_id);
  if (stream_info == nullptr) {
    LOG(DFATAL) << "Stream " << stream_id << " not registered";
  } else {
    child_vec.reserve(stream_info->children.size());
    for (StreamInfo* child : stream_info->children) {
      child_vec.push_back(child->id);
    }
  }
  return child_vec;
}

template <typename StreamIdType>
void Http2PriorityWriteScheduler<StreamIdType>::SetStreamWeight(
    StreamIdType stream_id,
    int weight) {
  if (stream_id == kHttp2RootStreamId) {
    LOG(DFATAL) << "Cannot set weight of root stream";
    return;
  }
  StreamInfo* stream_info = FindStream(stream_id);
  if (stream_info == nullptr) {
    LOG(DFATAL) << "Stream " << stream_id << " not registered";
    return;
  }
  weight = ClampWeight(weight);
  if (weight == stream_info->weight) {
    return;
  }
  if (stream_info->parent != nullptr) {
    stream_info->parent->total_child_weights += (weight - stream_info->weight);
  }
  stream_info->weight = weight;

  // Change in weight also affects sibling priorities.
  UpdatePrioritiesUnder(stream_info->parent);
}

template <typename StreamIdType>
void Http2PriorityWriteScheduler<StreamIdType>::SetStreamParent(
    StreamIdType stream_id,
    StreamIdType parent_id,
    bool exclusive) {
  if (stream_id == kHttp2RootStreamId) {
    LOG(DFATAL) << "Cannot set parent of root stream";
    return;
  }
  if (stream_id == parent_id) {
    LOG(DFATAL) << "Cannot set stream to be its own parent";
    return;
  }
  StreamInfo* stream_info = FindStream(stream_id);
  if (stream_info == nullptr) {
    LOG(DFATAL) << "Stream " << stream_id << " not registered";
    return;
  }
  StreamInfo* new_parent = FindStream(parent_id);
  if (new_parent == nullptr) {
    LOG(DFATAL) << "Parent stream " << parent_id << " not registered";
    return;
  }

  // If the new parent is already the stream's parent, we're done.
  if (stream_info->parent == new_parent) {
    return;
  }

  // Next, check to see if the new parent is currently a descendant
  // of the stream.
  StreamInfo* last = new_parent->parent;
  bool cycle_exists = false;
  while (last != nullptr) {
    if (last == stream_info) {
      cycle_exists = true;
      break;
    }
    last = last->parent;
  }

  if (cycle_exists) {
    // The new parent moves to the level of the current stream.
    SetStreamParent(parent_id, stream_info->parent->id, false);
  }

  // Remove stream from old parent's child list.
  StreamInfo* old_parent = stream_info->parent;
  Remove(&old_parent->children, stream_info);
  old_parent->total_child_weights -= stream_info->weight;
  UpdatePrioritiesUnder(old_parent);

  if (exclusive) {
    // Move the new parent's current children below the current stream.
    for (StreamInfo* child : new_parent->children) {
      child->parent = stream_info;
      stream_info->children.push_back(child);
    }
    stream_info->total_child_weights += new_parent->total_child_weights;
    // Clear new parent's old child data.
    new_parent->children.clear();
    new_parent->total_child_weights = 0;
  }

  // Make the change.
  stream_info->parent = new_parent;
  new_parent->children.push_back(stream_info);
  new_parent->total_child_weights += stream_info->weight;
  UpdatePrioritiesUnder(new_parent);
}

template <typename StreamIdType>
void Http2PriorityWriteScheduler<StreamIdType>::MarkStreamBlocked(
    StreamIdType stream_id,
    bool blocked) {
  if (stream_id == kHttp2RootStreamId) {
    LOG(DFATAL) << "Cannot mark root stream blocked or unblocked";
    return;
  }
  StreamInfo* stream_info = FindStream(stream_id);
  if (stream_info == nullptr) {
    LOG(DFATAL) << "Stream " << stream_id << " not registered";
    return;
  }
  stream_info->blocked = blocked;
  UpdateScheduling(stream_info);
}

template <typename StreamIdType>
void Http2PriorityWriteScheduler<StreamIdType>::MarkStreamReady(
    StreamIdType stream_id,
    bool ready) {
  if (stream_id == kHttp2RootStreamId) {
    LOG(DFATAL) << "Cannot mark root stream ready or unready";
    return;
  }
  StreamInfo* stream_info = FindStream(stream_id);
  if (stream_info == nullptr) {
    LOG(DFATAL) << "Stream " << stream_id << " not registered";
    return;
  }
  stream_info->ready = ready;
  UpdateScheduling(stream_info);
}

template <typename StreamIdType>
bool Http2PriorityWriteScheduler<StreamIdType>::Remove(
    StreamInfoVector* stream_infos,
    const StreamInfo* stream_info) {
  for (typename StreamInfoVector::iterator it = stream_infos->begin();
       it != stream_infos->end(); ++it) {
    if (*it == stream_info) {
      stream_infos->erase(it);
      return true;
    }
  }
  return false;
}

template <typename StreamIdType>
int Http2PriorityWriteScheduler<StreamIdType>::ClampWeight(int weight) {
  if (weight < kHttp2MinStreamWeight) {
    LOG(DFATAL) << "Invalid weight: " << weight;
    return kHttp2MinStreamWeight;
  }
  if (weight > kHttp2MaxStreamWeight) {
    LOG(DFATAL) << "Invalid weight: " << weight;
    return kHttp2MaxStreamWeight;
  }
  return weight;
}

template <typename StreamIdType>
bool Http2PriorityWriteScheduler<StreamIdType>::HasScheduledAncestor(
    const StreamInfo& stream_info) {
  for (const StreamInfo* parent = stream_info.parent; parent != nullptr;
       parent = parent->parent) {
    if (parent->scheduled) {
      return true;
    }
  }
  return false;
}

template <typename StreamIdType>
const typename Http2PriorityWriteScheduler<StreamIdType>::StreamInfo*
Http2PriorityWriteScheduler<StreamIdType>::FindStream(
    StreamIdType stream_id) const {
  typename StreamInfoMap::const_iterator it = all_stream_infos_.find(stream_id);
  return it == all_stream_infos_.end() ? nullptr : it->second;
}

template <typename StreamIdType>
typename Http2PriorityWriteScheduler<StreamIdType>::StreamInfo*
Http2PriorityWriteScheduler<StreamIdType>::FindStream(StreamIdType stream_id) {
  typename StreamInfoMap::iterator it = all_stream_infos_.find(stream_id);
  return it == all_stream_infos_.end() ? nullptr : it->second;
}

template <typename StreamIdType>
void Http2PriorityWriteScheduler<StreamIdType>::UpdatePrioritiesUnder(
    StreamInfo* stream_info) {
  for (StreamInfo* child : stream_info->children) {
    child->priority = stream_info->priority *
                      (static_cast<float>(child->weight) /
                       static_cast<float>(stream_info->total_child_weights));
    if (child->scheduled) {
      // Reposition in scheduling_queue_. Use post-order for scheduling, to
      // benefit from the fact that children have priority <= parent priority.
      Unschedule(child);
      UpdatePrioritiesUnder(child);
      Schedule(child);
    } else {
      UpdatePrioritiesUnder(child);
    }
  }
}

template <typename StreamIdType>
void Http2PriorityWriteScheduler<StreamIdType>::UpdateScheduling(
    StreamInfo* stream_info) {
  if (stream_info->IsSchedulable() != stream_info->scheduled) {
    if (stream_info->scheduled) {
      Unschedule(stream_info);
    } else {
      stream_info->ordinal = next_ordinal_++;
      Schedule(stream_info);
    }
  }
}

template <typename StreamIdType>
void Http2PriorityWriteScheduler<StreamIdType>::Schedule(
    StreamInfo* stream_info) {
  DCHECK(!stream_info->scheduled);
  for (base::LinkNode<StreamInfo>* s = scheduling_queue_.head();
       s != scheduling_queue_.end(); s = s->next()) {
    if (stream_info->SchedulesBefore(*s->value())) {
      stream_info->InsertBefore(s);
      stream_info->scheduled = true;
      break;
    }
  }
  if (!stream_info->scheduled) {
    stream_info->InsertAfter(scheduling_queue_.tail());
    stream_info->scheduled = true;
  }
}

template <typename StreamIdType>
void Http2PriorityWriteScheduler<StreamIdType>::Unschedule(
    StreamInfo* stream_info) {
  DCHECK(stream_info->scheduled);
  stream_info->RemoveFromList();
  stream_info->scheduled = false;
}

template <typename StreamIdType>
bool Http2PriorityWriteScheduler<StreamIdType>::StreamHasChild(
    StreamIdType parent_id,
    StreamIdType child_id) const {
  const StreamInfo* parent = FindStream(parent_id);
  if (parent == nullptr) {
    LOG(DFATAL) << "Parent stream " << parent_id << " not registered";
    return false;
  }
  if (!StreamRegistered(child_id)) {
    LOG(DFATAL) << "Child stream " << child_id << " not registered";
    return false;
  }
  auto found = std::find_if(parent->children.begin(), parent->children.end(),
                            [child_id](StreamInfo* stream_info) {
                              return stream_info->id == child_id;
                            });
  return found != parent->children.end();
}

template <typename StreamIdType>
bool Http2PriorityWriteScheduler<StreamIdType>::HasUsableStreams() const {
  // Even though not every stream in scheduling queue is guaranteed to be
  // usable (since children are occluded by parents), the presence of any
  // streams guarantees at least one is usable.
  return !scheduling_queue_.empty();
}

template <typename StreamIdType>
StreamIdType Http2PriorityWriteScheduler<StreamIdType>::PopNextUsableStream() {
  for (base::LinkNode<StreamInfo>* s = scheduling_queue_.head();
       s != scheduling_queue_.end(); s = s->next()) {
    StreamInfo* stream_info = s->value();
    if (!HasScheduledAncestor(*stream_info)) {
      stream_info->ready = false;
      Unschedule(stream_info);
      return stream_info->id;
    }
  }
  LOG(DFATAL) << "No usable streams";
  return kHttp2RootStreamId;
}

template <typename StreamIdType>
bool Http2PriorityWriteScheduler<StreamIdType>::ValidateInvariantsForTests()
    const {
  int total_streams = 0;
  int streams_visited = 0;
  // Iterate through all streams in the map.
  for (const auto& kv : all_stream_infos_) {
    ++total_streams;
    ++streams_visited;
    const StreamInfo& stream_info = *kv.second;
    // All streams except the root should have a parent, and should appear in
    // the children of that parent.
    if (stream_info.id != kHttp2RootStreamId &&
        !StreamHasChild(stream_info.parent->id, stream_info.id)) {
      DLOG(INFO) << "Parent stream " << stream_info.parent->id
                 << " is not registered, or does not list stream "
                 << stream_info.id << " as its child.";
      return false;
    }

    if (!stream_info.children.empty()) {
      int total_child_weights = 0;
      // Iterate through the stream's children.
      for (StreamInfo* child : stream_info.children) {
        ++streams_visited;
        // Each stream in the list should exist and should have this stream
        // set as its parent.
        if (!StreamRegistered(child->id) ||
            stream_info.id != GetStreamParent(child->id)) {
          DLOG(INFO) << "Child stream " << child->id << " is not registered, "
                     << "or does not list " << stream_info.id
                     << " as its parent.";
          return false;
        }
        total_child_weights += child->weight;
      }
      // Verify that total_child_weights is correct.
      if (total_child_weights != stream_info.total_child_weights) {
        DLOG(INFO) << "Child weight totals do not agree. For stream "
                   << stream_info.id << " total_child_weights has value "
                   << stream_info.total_child_weights << ", expected "
                   << total_child_weights;
        return false;
      }
    }
  }

  // Make sure num_streams reflects the total number of streams the map
  // contains.
  if (total_streams != num_streams()) {
    DLOG(INFO) << "Map contains incorrect number of streams.";
    return false;
  }
  // Validate the validation function; we should have visited each stream twice
  // (except for the root)
  DCHECK(streams_visited == 2 * num_streams() - 1);
  return true;
}

}  // namespace net

#endif  // NET_SPDY_HTTP2_WRITE_SCHEDULER_H_