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 daaa60e Fix Http/2 priority crashes. daaa60e is described below commit daaa60e5512358270c1b62d4d7c0226f94ccb4b2 Author: Susan Hinrichs <shinr...@oath.com> AuthorDate: Tue Aug 7 16:52:54 2018 +0000 Fix Http/2 priority crashes. (cherry picked from commit 8d982c8cd77923ac5ca8276a20dcabc18ee3c6fa) --- proxy/http2/Http2DependencyTree.h | 29 ++++++++-- proxy/http2/test_Http2DependencyTree.cc | 96 +++++++++++++++++++++++++++++++++ 2 files changed, 121 insertions(+), 4 deletions(-) diff --git a/proxy/http2/Http2DependencyTree.h b/proxy/http2/Http2DependencyTree.h index 5df9537..72cbd30 100644 --- a/proxy/http2/Http2DependencyTree.h +++ b/proxy/http2/Http2DependencyTree.h @@ -124,6 +124,7 @@ private: Node *_find(Node *node, uint32_t id, uint32_t depth = 1); Node *_top(Node *node); void _change_parent(Node *new_parent, Node *node, bool exclusive); + bool in_parent_chain(Node *maybe_parent, Node *target); Node *_root = new Node(this); uint32_t _max_depth; @@ -301,7 +302,10 @@ Tree<T>::reprioritize(Node *node, uint32_t new_parent_id, bool exclusive) if (new_parent == nullptr) { return; } - _change_parent(new_parent, old_parent, false); + // 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 @@ -310,6 +314,19 @@ Tree<T>::reprioritize(Node *node, uint32_t new_parent_id, bool exclusive) } } +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 @@ -338,11 +355,13 @@ Tree<T>::_change_parent(Node *node, Node *new_parent, bool exclusive) } 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()) { @@ -400,9 +419,11 @@ Tree<T>::deactivate(Node *node, uint32_t sent) { node->active = false; - while (node->queue->empty() && node->parent != nullptr) { - node->parent->queue->erase(node->entry); - node->queued = false; + while (!node->active && node->queue->empty() && node->parent != nullptr) { + if (node->queued) { + node->parent->queue->erase(node->entry); + node->queued = false; + } node = node->parent; } diff --git a/proxy/http2/test_Http2DependencyTree.cc b/proxy/http2/test_Http2DependencyTree.cc index 20ee49c..e735318 100644 --- a/proxy/http2/test_Http2DependencyTree.cc +++ b/proxy/http2/test_Http2DependencyTree.cc @@ -657,6 +657,102 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_3)(RegressionTest *t, int /* at delete tree; } +/** + * https://github.com/apache/trafficserver/issues/4057 + * Reprioritization to root + * + * x x + * | / \ + * A A D + * / \ / \ | + * B C ==> B C F + * / \ | + * D E E + * | + * F + */ +REGRESSION_TEST(Http2DependencyTree_reprioritize_4)(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"), f("F"); + + tree->add(0, 1, 0, false, &a); + tree->add(1, 3, 0, false, &b); + tree->add(1, 5, 0, false, &c); + tree->add(5, 7, 0, false, &d); + tree->add(5, 9, 0, false, &e); + tree->add(7, 11, 0, false, &f); + + Node *node_x = tree->find(0); + Node *node_a = tree->find(1); + Node *node_c = tree->find(5); + Node *node_d = tree->find(7); + Node *node_f = tree->find(11); + + tree->activate(node_f); + tree->reprioritize(7, 0, false); + + box.check(!node_a->queue->in(node_f->entry), "F should not be in A's queue"); + box.check(node_d->queue->in(node_f->entry), "F should be in D's queue"); + box.check(node_x->queue->in(node_d->entry), "D should be in x's queue"); + box.check(!node_a->queue->in(node_c->entry), "C should not be in A's queue"); + box.check(node_c->queue->empty(), "C's queue should be empty"); + + delete tree; +} + +/** + * https://github.com/apache/trafficserver/issues/4057 + * Reprioritization to unrelated node + * + * x x + * | | + * A A + * / \ / \ + * B C ==> B C + * / \ | | + * D E D E + * | | + * F F + */ +REGRESSION_TEST(Http2DependencyTree_reprioritize_5)(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"), f("F"); + + tree->add(0, 1, 0, false, &a); + tree->add(1, 3, 0, false, &b); + tree->add(1, 5, 0, false, &c); + tree->add(5, 7, 0, false, &d); + tree->add(5, 9, 0, false, &e); + tree->add(7, 11, 0, false, &f); + + Node *node_x = tree->find(0); + Node *node_a = tree->find(1); + Node *node_b = tree->find(3); + Node *node_c = tree->find(5); + Node *node_d = tree->find(7); + Node *node_f = tree->find(11); + + tree->activate(node_f); + tree->reprioritize(7, 3, false); + + box.check(node_a->queue->in(node_b->entry), "B should be in A's queue"); + box.check(node_b->queue->in(node_d->entry), "D should be in B's queue"); + box.check(!node_c->queue->in(node_d->entry), "D should not be in C's queue"); + box.check(node_x->queue->in(node_a->entry), "A should be in x's queue"); + box.check(!node_a->queue->in(node_c->entry), "C should not be in A's queue"); + box.check(node_c->queue->empty(), "C's queue should be empty"); + + delete tree; +} + /** test for https://github.com/apache/trafficserver/issues/2268 * * root root root