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 <shinr...@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; }