include/proxy/http2/Http2DependencyTree.h

/** @file

  HTTP/2 Dependency Tree

  The original idea of Stream Priority Algorithm using Weighted Fair Queue (WFQ)
  Scheduling is invented by Kazuho Oku (H2O project).

  @section license License

  Licensed to the Apache Software Foundation (ASF) under one
  or more contributor license agreements.  See the NOTICE file
  distributed with this work for additional information
  regarding copyright ownership.  The ASF licenses this file
  to you under the Apache License, Version 2.0 (the
  "License"); you may not use this file except in compliance
  with the License.  You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the specific language governing permissions and
  limitations under the License.
 */

#pragma once

#include <memory>

#include "tscore/List.h"
#include "tscore/Diags.h"
#include "tscore/PriorityQueue.h"

#include "proxy/http2/HTTP2.h"

// TODO: K is a constant, 256 is temporal value.
const static uint32_t K                               = 256;
const static uint32_t HTTP2_DEPENDENCY_TREE_MAX_DEPTH = 256;

namespace Http2DependencyTree
{
class Node
{
public:
  explicit Node(void *t = nullptr) : t(t)
  {
    entry = std::make_unique<PriorityQueueEntry<Node *>>(this);
    queue = std::make_unique<PriorityQueue<Node *>>();
  }

  Node(uint32_t i, uint32_t w, uint32_t p, Node *n, void *t = nullptr) : id(i), weight(w), point(p), t(t), parent(n)
  {
    entry = std::make_unique<PriorityQueueEntry<Node *>>(this);
    queue = std::make_unique<PriorityQueue<Node *>>();
  }

  ~Node()
  {
    // delete all child nodes
    if (!children.empty()) {
      Node *node = children.head;
      Node *next = nullptr;
      while (node) {
        next = node->link.next;
        children.remove(node);
        delete node;
        node = next;
      }
    }
  }

  Node(const Node &)            = delete;
  Node &operator=(const Node &) = delete;

  LINK(Node, link);

  bool
  operator<(const Node &n) const
  {
    return point < n.point;
  }

  bool
  operator>(const Node &n) const
  {
    return point > n.point;
  }

  /**
   * Added an explicit shadow flag.  The original logic
   * was using an null Http2Stream frame to mark a shadow node
   * but that would pull in Priority holder nodes too
   */
  bool
  is_shadow() const
  {
    return shadow == true;
  }

  bool                                        active = false;
  bool                                        queued = false;
  bool                                        shadow = false;
  uint32_t                                    id     = HTTP2_PRIORITY_DEFAULT_STREAM_DEPENDENCY;
  uint32_t                                    weight = HTTP2_PRIORITY_DEFAULT_WEIGHT;
  uint32_t                                    point  = 0;
  void                                       *t      = nullptr;
  Node                                       *parent = nullptr;
  DLL<Node>                                   children;
  std::unique_ptr<PriorityQueueEntry<Node *>> entry;
  std::unique_ptr<PriorityQueue<Node *>>      queue;
};

template <typename T> class Tree
{
public:
  explicit Tree(uint32_t max_concurrent_streams) : _max_depth(MIN(max_concurrent_streams, HTTP2_DEPENDENCY_TREE_MAX_DEPTH))
  {
    _ancestors.resize(_max_ancestors);
  }
  ~Tree() { delete _root; }
  Node    *find(uint32_t id, bool *is_max_leaf = nullptr);
  Node    *find_shadow(uint32_t id, bool *is_max_leaf = nullptr);
  Node    *add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t, bool shadow = false);
  Node    *reprioritize(uint32_t id, uint32_t new_parent_id, bool exclusive);
  Node    *reprioritize(Node *node, uint32_t id, bool exclusive);
  Node    *top();
  void     remove(Node *node);
  void     activate(Node *node);
  void     deactivate(Node *node, uint32_t sent);
  void     update(Node *node, uint32_t sent);
  bool     in(Node *current, Node *node);
  uint32_t size() const;
  /*
   * Dump the priority tree relationships in JSON form for debugging
   */
  void
  dump_tree(std::ostream &output) const
  {
    _dump(_root, output);
  }
  void     add_ancestor(Node *node);
  uint32_t was_ancestor(uint32_t id) const;

private:
  void  _dump(Node *node, std::ostream &output) const;
  Node *_find(Node *node, uint32_t id, uint32_t depth = 1, bool *is_max_leaf = nullptr);
  Node *_top(Node *node);
  void  _change_parent(Node *node, Node *new_parent, bool exclusive);
  bool  in_parent_chain(Node *maybe_parent, Node *target);

  Node    *_root = new Node(this);
  uint32_t _max_depth;
  uint32_t _node_count = 0;
  /*
   * _ancestors in a circular buffer tracking parent relationships for
   * recently completed nodes.  Without this new streams may not find their
   * parents and be inserted at the root, violating the client's desired
   * dependency relationship.  This addresses the issue identified in section
   * 5.3.4 of the HTTP/2 spec
   *
   * "It is possible for a stream to become closed while prioritization
   * information that creates a dependency on that stream is in transit.
   * If a stream identified in a dependency has no associated priority
   * information, then the dependent stream is instead assigned a default
   * priority (Section 5.3.5).  This potentially creates suboptimal
   * prioritization, since the stream could be given a priority that is
   * different from what is intended.
   * To avoid these problems, an endpoint SHOULD retain stream
   * prioritization state for a period after streams become closed.  The
   * longer state is retained, the lower the chance that streams are
   * assigned incorrect or default priority values."
   */
  static const uint32_t                      _max_ancestors  = 64;
  uint32_t                                   _ancestor_index = 0;
  std::vector<std::pair<uint32_t, uint32_t>> _ancestors;
};

template <typename T>
void
Tree<T>::_dump(Node *node, std::ostream &output) const
{
  output << R"({ "id":")" << node->id << "/" << node->weight << "/" << node->point << "/" << ((node->t != nullptr) ? "1" : "0")
         << "/" << ((node->active) ? "a" : "d") << "\",";
  // Dump the children
  output << " \"c\":[";
  for (Node *n = node->children.head; n; n = n->link.next) {
    _dump(n, output);
    output << ",";
  }
  output << "] }";
}

template <typename T>
Node *
Tree<T>::_find(Node *node, uint32_t id, uint32_t depth, bool *is_max_leaf)
{
  if (node->id == id) {
    if (is_max_leaf) {
      *is_max_leaf = depth == _max_depth;
    }
    return node;
  }

  if (node->children.empty() || depth > _max_depth) {
    return nullptr;
  }

  Node *result = nullptr;
  for (Node *n = node->children.head; n; n = n->link.next) {
    result = _find(n, id, ++depth, is_max_leaf);
    if (result != nullptr) {
      break;
    }
  }

  return result;
}

template <typename T>
Node *
Tree<T>::find_shadow(uint32_t id, bool *is_max_leaf)
{
  return _find(_root, id, 1, is_max_leaf);
}

template <typename T>
Node *
Tree<T>::find(uint32_t id, bool *is_max_leaf)
{
  Node *n = _find(_root, id, 1, is_max_leaf);
  return n == nullptr ? nullptr : (n->is_shadow() ? nullptr : n);
}

template <typename T>
void
Tree<T>::add_ancestor(Node *node)
{
  if (node->parent != _root) {
    _ancestors[_ancestor_index].first  = node->id;
    _ancestors[_ancestor_index].second = node->parent->id;
    _ancestor_index++;
    if (_ancestor_index >= _max_ancestors) {
      _ancestor_index = 0;
    }
  }
}

template <typename T>
uint32_t
Tree<T>::was_ancestor(uint32_t pid) const
{
  uint32_t i = (_ancestor_index == 0) ? _max_ancestors - 1 : _ancestor_index - 1;
  while (i != _ancestor_index) {
    if (_ancestors[i].first == pid) {
      return _ancestors[i].second;
    }
    i = (i == 0) ? _max_ancestors - 1 : i - 1;
  }
  return 0;
}

template <typename T>
Node *
Tree<T>::add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t, bool shadow)
{
  // Can we vivify a shadow node?
  Node *node = find_shadow(id);
  if (node != nullptr && node->is_shadow()) {
    node->t      = t;
    node->point  = id;
    node->weight = weight;
    node->shadow = false;
    // Move the shadow node into the proper position in the tree
    node = reprioritize(node, parent_id, exclusive);
    return node;
  }

  bool  is_max_leaf = false;
  Node *parent      = find_shadow(parent_id, &is_max_leaf); // Look for real and shadow nodes

  if (parent == nullptr) {
    if (parent_id < id) { // See if we still have a history of the parent
      uint32_t pid = parent_id;
      do {
        pid = was_ancestor(pid);
        if (pid != 0) {
          parent = find(pid);
        }
      } while (pid != 0 && parent == nullptr);
      if (parent == nullptr) {
        // Found no ancestor, just add to root at default weight
        weight    = HTTP2_PRIORITY_DEFAULT_WEIGHT;
        exclusive = false;
        parent    = _root;
      }
    }
    if (parent == nullptr || parent == _root) { // Create a shadow node
      parent    = add(0, parent_id, HTTP2_PRIORITY_DEFAULT_WEIGHT, false, nullptr, true);
      exclusive = false;
    }
  } else if (is_max_leaf) { // Chain too long, just add to root
    parent    = _root;
    exclusive = false;
  }

  // Use stream id as initial point
  node = new Node(id, weight, id, parent, t);

  if (exclusive) {
    while (Node *child = parent->children.pop()) {
      if (child->queued) {
        parent->queue->erase(child->entry.get());
        node->queue->push(child->entry.get());
      }
      node->children.push(child);
      child->parent = node;
    }
  }

  parent->children.push(node);
  if (!node->queue->empty()) {
    ink_release_assert(!node->queued);
    parent->queue->push(node->entry.get());
    node->queued = true;
  }
  node->shadow = shadow;
  ++_node_count;
  return node;
}

template <typename T>
bool
Tree<T>::in(Node *current, Node *node)
{
  bool retval = false;
  if (current == nullptr)
    current = _root;
  if (current->queue->in(node->entry.get())) {
    return true;
  } else {
    Node *child = current->children.head;
    while (child) {
      if (in(child, node)) {
        return true;
      }
      child = child->link.next;
    }
  }
  return retval;
}

template <typename T>
void
Tree<T>::remove(Node *node)
{
  if (node == _root || node->active) {
    return;
  }

  // Make a note of node's ancestry
  add_ancestor(node);

  Node *parent = node->parent;
  parent->children.remove(node);
  if (node->queued) {
    parent->queue->erase(node->entry.get());
  }

  // Push queue entries
  while (!node->queue->empty()) {
    parent->queue->push(node->queue->top());
    node->queue->pop();
  }

  // Push children
  while (!node->children.empty()) {
    Node *child = node->children.pop();
    parent->children.push(child);
    child->parent = parent;
  }

  // delete the shadow parent
  if (parent->is_shadow() && parent->children.empty() && parent->queue->empty()) {
    remove(parent);
  }

  // ink_release_assert(!this->in(nullptr, node));

  --_node_count;
  delete node;
}

template <typename T>
Node *
Tree<T>::reprioritize(uint32_t id, uint32_t new_parent_id, bool exclusive)
{
  Node *node = find(id);
  if (node == nullptr) {
    return node;
  }

  return reprioritize(node, new_parent_id, exclusive);
}

template <typename T>
Node *
Tree<T>::reprioritize(Node *node, uint32_t new_parent_id, bool exclusive)
{
  if (node == nullptr) {
    return node;
  }

  Node *old_parent = node->parent;
  if (old_parent->id == new_parent_id) {
    // Do nothing
    return node;
  }
  // should not change the root node
  ink_assert(node->parent);

  Node *new_parent = find(new_parent_id);
  if (new_parent == nullptr) {
    return node;
  }
  // If node is dependent on the new parent, must move the new parent first
  if (new_parent_id != 0 && in_parent_chain(node, new_parent)) {
    _change_parent(new_parent, old_parent, false);
  }
  _change_parent(node, new_parent, exclusive);

  // delete the shadow node
  if (node->is_shadow() && node->children.empty() && node->queue->empty()) {
    remove(node);
    return nullptr;
  }

  return node;
}

template <typename T>
bool
Tree<T>::in_parent_chain(Node *maybe_parent, Node *target)
{
  bool  retval = false;
  Node *parent = target->parent;
  while (parent != nullptr && !retval) {
    retval = maybe_parent == parent;
    parent = parent->parent;
  }
  return retval;
}

// Change node's parent to new_parent
template <typename T>
void
Tree<T>::_change_parent(Node *node, Node *new_parent, bool exclusive)
{
  ink_release_assert(node->parent != nullptr);
  node->parent->children.remove(node);
  if (node->queued) {
    node->parent->queue->erase(node->entry.get());
    node->queued = false;

    Node *current = node->parent;
    while (current->queue->empty() && !current->active && current->parent != nullptr) {
      current->parent->queue->erase(current->entry.get());
      current->queued = false;
      current         = current->parent;
    }
  }

  node->parent = nullptr;
  if (exclusive) {
    while (Node *child = new_parent->children.pop()) {
      if (child->queued) {
        child->parent->queue->erase(child->entry.get());
        node->queue->push(child->entry.get());
      }

      node->children.push(child);
      ink_release_assert(child != node);
      child->parent = node;
    }
  }

  new_parent->children.push(node);
  ink_release_assert(node != new_parent);
  node->parent = new_parent;

  if (node->active || !node->queue->empty()) {
    Node *current = node;
    while (current->parent != nullptr && !current->queued) {
      current->parent->queue->push(current->entry.get());
      current->queued = true;
      current         = current->parent;
    }
  }
}

template <typename T>
Node *
Tree<T>::_top(Node *node)
{
  Node *child = node;

  while (child != nullptr) {
    if (child->active) {
      return child;
    } else if (!child->queue->empty()) {
      child = child->queue->top()->node;
    } else {
      return nullptr;
    }
  }

  return child;
}

template <typename T>
Node *
Tree<T>::top()
{
  return _top(_root);
}

template <typename T>
void
Tree<T>::activate(Node *node)
{
  node->active = true;

  while (node->parent != nullptr && !node->queued) {
    node->parent->queue->push(node->entry.get());
    node->queued = true;
    node         = node->parent;
  }
}

template <typename T>
void
Tree<T>::deactivate(Node *node, uint32_t sent)
{
  node->active = false;

  while (!node->active && node->queue->empty() && node->parent != nullptr) {
    if (node->queued) {
      node->parent->queue->erase(node->entry.get());
      node->queued = false;
    }

    node = node->parent;
  }

  update(node, sent);
}

template <typename T>
void
Tree<T>::update(Node *node, uint32_t sent)
{
  while (node->parent != nullptr) {
    node->point += sent * K / (node->weight + 1);

    if (node->queued) {
      node->parent->queue->update(node->entry.get(), true);
    } else {
      node->parent->queue->push(node->entry.get());
      node->queued = true;
    }

    node = node->parent;
  }
}

template <typename T>
uint32_t
Tree<T>::size() const
{
  return _node_count;
}
} // namespace Http2DependencyTree