You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by sh...@apache.org on 2018/09/20 15:22:31 UTC
[trafficserver] branch master updated: HTTP/2 priority fixes to
match common browser patterns
This is an automated email from the ASF dual-hosted git repository.
shinrich pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push:
new fc5fb69 HTTP/2 priority fixes to match common browser patterns
fc5fb69 is described below
commit fc5fb69cb0d5bf89a870cdc9e0558f4ade36c773
Author: Susan Hinrichs <sh...@apache.org>
AuthorDate: Wed Sep 5 08:18:42 2018 -0500
HTTP/2 priority fixes to match common browser patterns
---
proxy/http2/Http2ConnectionState.cc | 11 +++
proxy/http2/Http2DependencyTree.h | 157 +++++++++++++++++++++++++----
proxy/http2/test_Http2DependencyTree.cc | 170 ++++++++++++++++++++++++++++----
3 files changed, 300 insertions(+), 38 deletions(-)
diff --git a/proxy/http2/Http2ConnectionState.cc b/proxy/http2/Http2ConnectionState.cc
index 040a7e7..add8df7 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 Http2ConDebug(ua_session, fmt, ...) \
SsnDebug(ua_session, "http2_con", "[%" PRId64 "] " fmt, ua_session->connection_id(), ##__VA_ARGS__);
@@ -418,6 +419,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.
@@ -1196,6 +1202,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 936f5d5..7b71303 100644
--- a/proxy/http2/Http2DependencyTree.h
+++ b/proxy/http2/Http2DependencyTree.h
@@ -84,14 +84,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,12 +111,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);
@@ -120,9 +128,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);
@@ -130,23 +149,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;
}
@@ -157,36 +216,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);
@@ -207,7 +321,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;
}
@@ -241,6 +355,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 3595a84..c9ed43b 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;
}