trafficserver-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From zw...@apache.org
Subject [trafficserver] branch 7.1.x updated: HTTP/2 priority fixes to match common browser patterns
Date Mon, 08 Oct 2018 23:58:17 GMT
This is an automated email from the ASF dual-hosted git repository.

zwoop pushed a commit to branch 7.1.x
in repository https://gitbox.apache.org/repos/asf/trafficserver.git


The following commit(s) were added to refs/heads/7.1.x by this push:
     new 5efde47  HTTP/2 priority fixes to match common browser patterns
5efde47 is described below

commit 5efde47f2da501f659bb196d52d0a67fac86000d
Author: Susan Hinrichs <shinrich@apache.org>
AuthorDate: Wed Sep 5 08:18:42 2018 -0500

    HTTP/2 priority fixes to match common browser patterns
    
    (cherry picked from commit fc5fb69cb0d5bf89a870cdc9e0558f4ade36c773)
    
    Conflicts:
    	proxy/http2/Http2DependencyTree.h
---
 proxy/http2/Http2ConnectionState.cc     |  11 +++
 proxy/http2/Http2DependencyTree.h       | 157 +++++++++++++++++++++++++----
 proxy/http2/test_Http2DependencyTree.cc | 170 ++++++++++++++++++++++++++++----
 3 files changed, 301 insertions(+), 37 deletions(-)

diff --git a/proxy/http2/Http2ConnectionState.cc b/proxy/http2/Http2ConnectionState.cc
index e45e624..6652702 100644
--- a/proxy/http2/Http2ConnectionState.cc
+++ b/proxy/http2/Http2ConnectionState.cc
@@ -26,6 +26,7 @@
 #include "Http2ClientSession.h"
 #include "Http2Stream.h"
 #include "Http2DebugNames.h"
+#include <sstream>
 
 #define DebugHttp2Con(ua_session, fmt, ...) \
   DebugSsn(ua_session, "http2_con", "[%" PRId64 "] " fmt, ua_session->connection_id(),
##__VA_ARGS__);
@@ -405,6 +406,11 @@ rcv_priority_frame(Http2ConnectionState &cstate, const Http2Frame
&frame)
     // [RFC 7540] 5.3.3 Reprioritization
     Http2StreamDebug(cstate.ua_session, stream_id, "Reprioritize");
     cstate.dependency_tree->reprioritize(node, priority.stream_dependency, priority.exclusive_flag);
+    if (is_debug_tag_set("http2_priority")) {
+      std::stringstream output;
+      cstate.dependency_tree->dump_tree(output);
+      Debug("http2_priority", "[%" PRId64 "] reprioritize %s", cstate.ua_session->connection_id(),
output.str().c_str());
+    }
   } else {
     // PRIORITY frame is received before HEADERS frame.
 
@@ -1131,6 +1137,11 @@ Http2ConnectionState::delete_stream(Http2Stream *stream)
       if (node->active) {
         dependency_tree->deactivate(node, 0);
       }
+      if (is_debug_tag_set("http2_priority")) {
+        std::stringstream output;
+        dependency_tree->dump_tree(output);
+        Debug("http2_priority", "[%" PRId64 "] %s", ua_session->connection_id(), output.str().c_str());
+      }
       dependency_tree->remove(node);
       // ink_release_assert(dependency_tree->find(stream->get_id()) == nullptr);
     }
diff --git a/proxy/http2/Http2DependencyTree.h b/proxy/http2/Http2DependencyTree.h
index 72cbd30..51f34a5 100644
--- a/proxy/http2/Http2DependencyTree.h
+++ b/proxy/http2/Http2DependencyTree.h
@@ -29,6 +29,7 @@
 #include "ts/List.h"
 #include "ts/Diags.h"
 #include "ts/PriorityQueue.h"
+#include <vector>
 
 #include "HTTP2.h"
 
@@ -84,14 +85,20 @@ public:
     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 t == nullptr;
+    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;
@@ -105,11 +112,14 @@ public:
 template <typename T> class Tree
 {
 public:
-  Tree(uint32_t max_concurrent_streams) : _max_depth(MIN(max_concurrent_streams, HTTP2_DEPENDENCY_TREE_MAX_DEPTH))
{}
+  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);
-  Node *find_shadow(uint32_t id);
-  Node *add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t);
+  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);
   void remove(Node *node);
   void reprioritize(uint32_t new_parent_id, uint32_t id, bool exclusive);
   void reprioritize(Node *node, uint32_t id, bool exclusive);
@@ -119,9 +129,20 @@ public:
   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:
-  Node *_find(Node *node, uint32_t id, uint32_t depth = 1);
+  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 *new_parent, Node *node, bool exclusive);
   bool in_parent_chain(Node *maybe_parent, Node *target);
@@ -129,23 +150,63 @@ private:
   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 << "{ \"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)
+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) {
+  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);
+    result = _find(n, id, ++depth, is_max_leaf);
     if (result != nullptr) {
       break;
     }
@@ -156,36 +217,91 @@ Tree<T>::_find(Node *node, uint32_t id, uint32_t depth)
 
 template <typename T>
 Node *
-Tree<T>::find_shadow(uint32_t id)
+Tree<T>::find_shadow(uint32_t id, bool *is_max_leaf)
 {
-  return _find(_root, id);
+  return _find(_root, id, 1, is_max_leaf);
 }
 
 template <typename T>
 Node *
-Tree<T>::find(uint32_t id)
+Tree<T>::find(uint32_t id, bool *is_max_leaf)
 {
-  Node *n = _find(_root, id);
+  Node *n = _find(_root, id, 1, is_max_leaf);
   return n == nullptr ? nullptr : (n->is_shadow() ? nullptr : n);
 }
 
 template <typename T>
-Node *
-Tree<T>::add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t)
+void
+Tree<T>::add_ancestor(Node *node)
 {
-  Node *parent = find(parent_id);
-  if (parent == nullptr) {
-    parent = add(0, parent_id, HTTP2_PRIORITY_DEFAULT_WEIGHT, false, nullptr);
+  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
+    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);
 
@@ -206,7 +322,7 @@ Tree<T>::add(uint32_t parent_id, uint32_t id, uint32_t weight, bool
exclusive, T
     parent->queue->push(node->entry);
     node->queued = true;
   }
-
+  node->shadow = shadow;
   ++_node_count;
   return node;
 }
@@ -240,6 +356,9 @@ Tree<T>::remove(Node *node)
     return;
   }
 
+  // Make a note of node's ancestory
+  add_ancestor(node);
+
   Node *parent = node->parent;
   parent->children.remove(node);
   if (node->queued) {
diff --git a/proxy/http2/test_Http2DependencyTree.cc b/proxy/http2/test_Http2DependencyTree.cc
index e735318..b9c5696 100644
--- a/proxy/http2/test_Http2DependencyTree.cc
+++ b/proxy/http2/test_Http2DependencyTree.cc
@@ -778,21 +778,22 @@ REGRESSION_TEST(Http2DependencyTree_insert_with_empty_parent)(RegressionTest
*t,
 
   string a("A"), b("B"), c("C");
   tree->add(0, 3, 20, false, &a);
-  Node *b_n = tree->add(5, 7, 30, true, &b);
 
-  box.check(b_n->parent->id == 5, "Node B's parent should be 5");
-  box.check(tree->find(5) == nullptr, "The shadow nodes should not be found");
-  box.check(tree->find_shadow(5)->is_shadow() == true, "nodes 5 should be the shadow
node");
+  Node *b_n = tree->add(9, 7, 30, true, &b);
 
-  Node *c_n = tree->add(7, 9, 30, false, &c);
+  box.check(b_n->parent->id == 9, "Node B's parent should be 9");
+  box.check(tree->find(9) == nullptr, "The shadow nodes should not be found");
+  box.check(tree->find_shadow(9)->is_shadow() == true, "nodes 9 should be the shadow
node");
+
+  Node *c_n = tree->add(7, 11, 30, false, &c);
   tree->remove(b_n);
 
-  box.check(c_n->parent->id == 5, "Node C's parent should be 5");
+  box.check(c_n->parent->id == 9, "Node C's parent should be 9");
   box.check(tree->find(7) == nullptr, "Nodes b should be removed");
-  box.check(tree->find_shadow(5)->is_shadow() == true, "Nodes 5 should be existed after
removing");
+  box.check(tree->find_shadow(9)->is_shadow() == true, "Nodes 9 should be existed after
removing");
 
   tree->remove(c_n);
-  box.check(tree->find_shadow(5) == nullptr, "Shadow nodes should be remove");
+  box.check(tree->find_shadow(9) == nullptr, "Shadow nodes should be remove");
 
   delete tree;
 }
@@ -814,18 +815,147 @@ REGRESSION_TEST(Http2DependencyTree_shadow_reprioritize)(RegressionTest
*t, int
 
   string a("A"), b("B");
   tree->add(0, 3, 20, false, &a);
-  tree->add(5, 7, 30, true, &b);
+  tree->add(9, 7, 30, true, &b);
 
-  Node *s_n = tree->find_shadow(5);
+  Node *s_n = tree->find_shadow(9);
   box.check(s_n != nullptr && s_n->is_shadow() == true, "Shadow nodes should not
be nullptr");
 
   tree->reprioritize(s_n, 7, false);
-  box.check(tree->find_shadow(5) == nullptr, "Shadow nodes should be nullptr after reprioritizing");
+  box.check(tree->find_shadow(9) == nullptr, "Shadow nodes should be nullptr after reprioritizing");
+
+  delete tree;
+}
+
+/** Test for https://github.com/apache/trafficserver/pull/4212
+ *
+ * Add child to parent that has already completed.
+ *
+ * root        root        root        root       root
+ *  |           |           |           |          |
+ *  A   ====>   A   ====>   A   ====>   A  ====>   A
+ *  |                       |                      |
+ *  B                       C                      E
+ *                          |
+ *                          D
+ */
+REGRESSION_TEST(Http2DependencyTree_delete_parent_before_child_arrives)(RegressionTest *t,
int /* atype ATS_UNUSED */, int *pstatus)
+{
+  TestBox box(t, pstatus);
+  box = REGRESSION_TEST_PASSED;
+
+  Tree *tree = new Tree(100);
+  string a("A"), b("B"), c("C"), d("D"), e("E");
+
+  tree->add(0, 3, 20, false, &a);
+  Node *node_b = tree->add(3, 5, 30, true, &b);
+
+  tree->remove(node_b);
+
+  // Tree should remember B, so C will be added to B's ancestor
+  Node *node_c = tree->add(5, 7, 20, false, &c);
+  box.check(node_c->parent->id == 3, "Node C's parent should be 3");
+
+  // See if it remembers two missing ancestors
+  Node *node_d = tree->add(7, 9, 20, false, &d);
+
+  tree->remove(node_c);
+  tree->remove(node_d);
+
+  Node *node_e = tree->add(9, 11, 30, false, &e);
+  box.check(node_e->parent->id == 3, "Node E's parent should be 3");
 
   delete tree;
 }
 
-REGRESSION_TEST(Http2DependencyTree_shadow_change)(RegressionTest *t, int /* atype ATS_UNUSED
*/, int *pstatus)
+/** Test for https://github.com/apache/trafficserver/pull/4212
+ *
+ * Make sure priority nodes stick around
+ *
+ *        root                 root
+ *       / | \                / | \
+ *      P1 P2 P3   ====>     P1 P2 P3
+ *      |  |  |                 |  |
+ *      A  B  C                 B  C
+ *         |                    |
+ *         D                    D
+ */
+REGRESSION_TEST(Http2DependencyTree_handle_priority_nodes)(RegressionTest *t, int /* atype
ATS_UNUSED */, int *pstatus)
+{
+  TestBox box(t, pstatus);
+  box = REGRESSION_TEST_PASSED;
+
+  Tree *tree = new Tree(100);
+  string a("A"), b("B"), c("C"), d("D"), e("E");
+
+  // P1 node
+  tree->add(0, 3, 20, false, nullptr);
+  // P2 node
+  tree->add(0, 5, 20, false, nullptr);
+  // P3 node
+  tree->add(0, 7, 20, false, nullptr);
+
+  Node *node_a = tree->add(3, 9, 30, true, &a);
+  Node *node_b = tree->add(5, 11, 30, true, &b);
+  Node *node_c = tree->add(7, 13, 30, true, &c);
+  Node *node_d = tree->add(11, 15, 30, true, &d);
+
+  box.check(node_a->parent->id == 3, "Node A's parent should be 3");
+  box.check(node_b->parent->id == 5, "Node B's parent should be 5");
+  box.check(node_c->parent->id == 7, "Node C's parent should be 7");
+  box.check(node_d->parent->id == 11, "Node D's parent should be 11");
+
+  // Deleting the children should not make the priority node go away
+  tree->remove(node_a);
+  Node *node_p1 = tree->find(3);
+  box.check(node_p1 != nullptr, "Priority node 1 should remain");
+
+  delete tree;
+}
+
+/**
+ * Shadow nodes should reprioritize when they vivify
+ *
+ *      root                root              root
+ *      /  \                 |                 |
+ *     A   Shadow  ====>     A          ====>  A
+ *          |                |                 |
+ *          B                C(was shadow)     C
+ *                           |
+ *                           B
+ */
+REGRESSION_TEST(Http2DependencyTree_reprioritize_shadow_node)(RegressionTest *t, int /* atype
ATS_UNUSED */, int *pstatus)
+{
+  TestBox box(t, pstatus);
+  box = REGRESSION_TEST_PASSED;
+
+  Tree *tree = new Tree(100);
+  string a("A"), b("B"), c("C");
+
+  tree->add(0, 3, 20, false, &a);
+  // 7 should be created as a shadow node
+  tree->add(7, 5, 20, false, &b);
+
+  Node *b_n        = tree->find(5);
+  Node *c_n        = tree->find(7);
+  Node *c_shadow_n = tree->find_shadow(7);
+
+  box.check(b_n != nullptr && b_n->parent->id == 7, "B should be child of 7");
+  box.check(c_n == nullptr && c_shadow_n != nullptr && c_shadow_n->parent->id
== 0, "Node 7 is a shadow and a child of the root");
+
+  // Now populate the shadow
+  tree->add(3, 7, 30, false, &c);
+  c_n = tree->find(7);
+  box.check(c_n != nullptr && c_n->parent->id == 3 && c_n->weight
== 30, "C is a child of 3 and no longer a shadow");
+
+  // C should still exist when its child goes away
+  tree->remove(b_n);
+  c_n = tree->find(7);
+  box.check(c_n != nullptr, "C is still present with no children");
+
+  delete tree;
+}
+
+REGRESSION_TEST(Http2DependencyTree_missing_parent)(RegressionTest *t, int /* atype ATS_UNUSED
*/, int *pstatus)
 {
   TestBox box(t, pstatus);
   box = REGRESSION_TEST_PASSED;
@@ -836,9 +966,13 @@ REGRESSION_TEST(Http2DependencyTree_shadow_change)(RegressionTest *t,
int /* aty
   tree->add(0, 3, 20, false, &a);
   tree->add(5, 7, 30, true, &b);
 
+  Node *c_n        = tree->find(5);
+  Node *c_shadow_n = tree->find_shadow(5);
+  box.check(c_n == nullptr && c_shadow_n != nullptr && c_shadow_n->is_shadow()
== true, "Node 5 starts out as a shadow");
+
   tree->add(0, 5, 15, false, &c);
 
-  Node *c_n = tree->find(5);
+  c_n = tree->find(5);
   box.check(c_n != nullptr && c_n->is_shadow() == false, "Node 5 should not be
shadow node");
   box.check(c_n->point == 5 && c_n->weight == 15, "The weight and point should
be 15");
 
@@ -852,13 +986,13 @@ REGRESSION_TEST(Http2DependencyTree_max_depth)(RegressionTest *t, int
/* atype A
 
   Tree *tree = new Tree(100);
   string a("A");
-
-  for (int i = 0; i < 200; ++i) {
+  for (int i = 0; i < 100; ++i) {
     tree->add(i, i + 1, 16, false, &a);
   }
-
-  Node *node = tree->find(101);
-  box.check(node->parent->parent->id == 0, "101st node should be child of root's
child node");
+  Node *node = tree->find(100);
+  Node *leaf = tree->find(99);
+  box.check(node->parent->id == 0, "100st node should be child root");
+  box.check(leaf != nullptr && leaf->parent->id != 0, "99th node is not a child
of the root");
 
   delete tree;
 }


Mime
View raw message