You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by bc...@apache.org on 2018/10/11 17:19:04 UTC
[trafficserver] branch 8.0.x updated (1cf3cae -> 618961f)
This is an automated email from the ASF dual-hosted git repository.
bcall pushed a change to branch 8.0.x
in repository https://gitbox.apache.org/repos/asf/trafficserver.git.
from 1cf3cae Cache: update internal counters to be std::atomic.
new 1e83131 HTTP/2 priority fixes to match common browser patterns
new 618961f Test: Convert test_Http2DependencyTree.cc to Catch
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
proxy/http2/Http2ConnectionState.cc | 11 +
proxy/http2/Http2DependencyTree.h | 157 ++++++--
proxy/http2/Makefile.am | 5 +-
.../{ => unit_tests}/test_Http2DependencyTree.cc | 399 ++++++++++++---------
4 files changed, 385 insertions(+), 187 deletions(-)
rename proxy/http2/{ => unit_tests}/test_Http2DependencyTree.cc (63%)
[trafficserver] 02/02: Test: Convert test_Http2DependencyTree.cc to
Catch
Posted by bc...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
bcall pushed a commit to branch 8.0.x
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit 618961fb61d3590791b3084be6121893c0a04680
Author: Xavier Chi <ch...@gmail.com>
AuthorDate: Thu Sep 20 15:25:54 2018 -0500
Test: Convert test_Http2DependencyTree.cc to Catch
(cherry picked from commit 7cfa1af5548d1340b01a19d8f383b305cb59e743)
---
proxy/http2/Makefile.am | 5 +-
.../{ => unit_tests}/test_Http2DependencyTree.cc | 299 ++++++++-------------
2 files changed, 120 insertions(+), 184 deletions(-)
diff --git a/proxy/http2/Makefile.am b/proxy/http2/Makefile.am
index 7bbfda1..ad08f7e 100644
--- a/proxy/http2/Makefile.am
+++ b/proxy/http2/Makefile.am
@@ -80,8 +80,11 @@ test_Http2DependencyTree_LDADD = \
$(top_builddir)/src/tscore/libtscore.la \
$(top_builddir)/src/tscpp/util/libtscpputil.la
+test_Http2DependencyTree_CPPFLAGS = $(AM_CPPFLAGS)\
+ -I$(abs_top_srcdir)/tests/include
+
test_Http2DependencyTree_SOURCES = \
- test_Http2DependencyTree.cc \
+ unit_tests/test_Http2DependencyTree.cc \
Http2DependencyTree.h
test_HPACK_LDADD = \
diff --git a/proxy/http2/test_Http2DependencyTree.cc b/proxy/http2/unit_tests/test_Http2DependencyTree.cc
similarity index 64%
rename from proxy/http2/test_Http2DependencyTree.cc
rename to proxy/http2/unit_tests/test_Http2DependencyTree.cc
index c9ed43b..b72bbce 100644
--- a/proxy/http2/test_Http2DependencyTree.cc
+++ b/proxy/http2/unit_tests/test_Http2DependencyTree.cc
@@ -20,13 +20,13 @@
See the License for the specific language governing permissions and
limitations under the License.
*/
+#define CATCH_CONFIG_MAIN
+#include "catch.hpp"
#include <iostream>
#include <cstring>
#include <sstream>
-#include "tscore/TestBox.h"
-
#include "Http2DependencyTree.h"
using namespace std;
@@ -43,11 +43,8 @@ using Node = Http2DependencyTree::Node;
* / \
* B C
*/
-REGRESSION_TEST(Http2DependencyTree_1)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_1", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C"), d("D");
@@ -58,17 +55,17 @@ REGRESSION_TEST(Http2DependencyTree_1)(RegressionTest *t, int /* atype ATS_UNUSE
Node *node_b = tree->find(1);
Node *node_c = tree->find(3);
- box.check(node_b->parent == node_a, "parent of B should be A");
- box.check(node_c->parent == node_a, "parent of C should be A");
+ REQUIRE(node_b->parent == node_a);
+ REQUIRE(node_c->parent == node_a);
// Add node with exclusive flag
tree->add(0, 5, 0, true, &d);
Node *node_d = tree->find(5);
- box.check(node_d->parent == node_a, "parent of D should be A");
- box.check(node_b->parent == node_d, "parent of B should be D");
- box.check(node_c->parent == node_d, "parent of C should be D");
+ REQUIRE(node_d->parent == node_a);
+ REQUIRE(node_b->parent == node_d);
+ REQUIRE(node_c->parent == node_d);
delete tree;
}
@@ -86,11 +83,8 @@ REGRESSION_TEST(Http2DependencyTree_1)(RegressionTest *t, int /* atype ATS_UNUSE
* | |
* F E
*/
-REGRESSION_TEST(Http2DependencyTree_2)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_2", "[http2][Http2DependencyTree]")
{
- 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");
@@ -108,9 +102,9 @@ REGRESSION_TEST(Http2DependencyTree_2)(RegressionTest *t, int /* atype ATS_UNUSE
Node *node_d = tree->find(7);
Node *node_f = tree->find(11);
- box.check(node_a->parent == node_d, "parent of A should be D");
- box.check(node_d->parent == node_x, "parent of D should be X");
- box.check(node_f->parent == node_d, "parent of F should be D");
+ REQUIRE(node_a->parent == node_d);
+ REQUIRE(node_d->parent == node_x);
+ REQUIRE(node_f->parent == node_d);
delete tree;
}
@@ -128,11 +122,8 @@ REGRESSION_TEST(Http2DependencyTree_2)(RegressionTest *t, int /* atype ATS_UNUSE
* | |
* F E
*/
-REGRESSION_TEST(Http2DependencyTree_3)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_3", "[http2][Http2DependencyTree]")
{
- 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");
@@ -150,9 +141,9 @@ REGRESSION_TEST(Http2DependencyTree_3)(RegressionTest *t, int /* atype ATS_UNUSE
Node *node_d = tree->find(7);
Node *node_f = tree->find(11);
- box.check(node_a->parent == node_d, "parent of A should be D");
- box.check(node_d->parent == node_x, "parent of D should be X");
- box.check(node_f->parent == node_a, "parent of F should be A");
+ REQUIRE(node_a->parent == node_d);
+ REQUIRE(node_d->parent == node_x);
+ REQUIRE(node_f->parent == node_a);
delete tree;
}
@@ -163,24 +154,21 @@ REGRESSION_TEST(Http2DependencyTree_3)(RegressionTest *t, int /* atype ATS_UNUSE
* /
* A(1)
*/
-REGRESSION_TEST(Http2DependencyTree_4)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_4", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A");
tree->add(0, 1, 0, false, &a);
Node *node_a = tree->find(1);
- box.check(tree->top() == nullptr, "top should be nullptr");
+ REQUIRE(tree->top() == nullptr);
tree->activate(node_a);
- box.check(tree->top() == node_a, "top should be A");
+ REQUIRE(tree->top() == node_a);
tree->deactivate(node_a, 0);
- box.check(tree->top() == nullptr, "top should be nullptr");
+ REQUIRE(tree->top() == nullptr);
delete tree;
}
@@ -194,11 +182,8 @@ REGRESSION_TEST(Http2DependencyTree_4)(RegressionTest *t, int /* atype ATS_UNUSE
* B(5)
*
*/
-REGRESSION_TEST(Http2DependencyTree_5)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_5", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C");
@@ -208,14 +193,14 @@ REGRESSION_TEST(Http2DependencyTree_5)(RegressionTest *t, int /* atype ATS_UNUSE
Node *node_a = tree->find(3);
Node *node_b = tree->find(5);
- box.check(tree->top() == nullptr, "top should be nullptr");
+ REQUIRE(tree->top() == nullptr);
tree->activate(node_a);
tree->activate(node_b);
- box.check(tree->top() == node_a, "top should be A");
+ REQUIRE(tree->top() == node_a);
tree->deactivate(node_a, 0);
- box.check(tree->top() == node_b, "top should be B");
+ REQUIRE(tree->top() == node_b);
delete tree;
}
@@ -229,11 +214,8 @@ REGRESSION_TEST(Http2DependencyTree_5)(RegressionTest *t, int /* atype ATS_UNUSE
* B(5) C(7)
*
*/
-REGRESSION_TEST(Http2DependencyTree_6)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_6", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C"), d("D");
@@ -258,7 +240,7 @@ REGRESSION_TEST(Http2DependencyTree_6)(RegressionTest *t, int /* atype ATS_UNUSE
}
const string expect = "BDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBD";
- box.check(oss.str() == expect, "\nExpect : %s\nActual : %s", expect.c_str(), oss.str().c_str());
+ REQUIRE(oss.str() == expect);
delete tree;
}
@@ -271,11 +253,8 @@ REGRESSION_TEST(Http2DependencyTree_6)(RegressionTest *t, int /* atype ATS_UNUSE
* A(3) B(5) ... I(19)
*
*/
-REGRESSION_TEST(Http2DependencyTree_Chrome_50)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_Chrome_50", "[http2][Http2DependencyTree]")
{
- 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"), g("G"), h("H"), i("I");
@@ -313,7 +292,7 @@ REGRESSION_TEST(Http2DependencyTree_Chrome_50)(RegressionTest *t, int /* atype A
const string expect =
"ABCDEFGHIABCDEFGHIABCDEFABCGHIABCDEFABCGHIDEFABCGHIDEFABCABCDEFGHIABCDEFABCGHIABCDEFABCGHIDEFABCGHIDEFABCABC";
- box.check(oss.str() == expect, "\nExpect : %s\nActual : %s", expect.c_str(), oss.str().c_str());
+ REQUIRE(oss.str() == expect);
delete tree;
}
@@ -332,11 +311,8 @@ REGRESSION_TEST(Http2DependencyTree_Chrome_50)(RegressionTest *t, int /* atype A
* I(19)
*
*/
-REGRESSION_TEST(Http2DependencyTree_Chrome_51)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_Chrome_51", "[http2][Http2DependencyTree]")
{
- 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"), g("G"), h("H"), i("I");
@@ -388,7 +364,7 @@ REGRESSION_TEST(Http2DependencyTree_Chrome_51)(RegressionTest *t, int /* atype A
const string expect = "ACEGIBDFH";
- box.check(oss.str() == expect, "\nExpect : %s\nActual : %s", expect.c_str(), oss.str().c_str());
+ REQUIRE(oss.str() == expect);
delete tree;
}
@@ -403,11 +379,8 @@ REGRESSION_TEST(Http2DependencyTree_Chrome_51)(RegressionTest *t, int /* atype A
* B(5) C(7)
*
*/
-REGRESSION_TEST(Http2DependencyTree_remove_1)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_remove_1", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C");
@@ -426,24 +399,24 @@ REGRESSION_TEST(Http2DependencyTree_remove_1)(RegressionTest *t, int /* atype AT
// Deactivate A and try to remove
top_node = tree->top();
- box.check(top_node == node_a, "Top node should be node_a");
+ REQUIRE(top_node == node_a);
tree->deactivate(node_a, 16);
tree->remove(node_a);
- box.check(tree->find(3) == nullptr, "Node A should be removed");
+ REQUIRE(tree->find(3) == nullptr);
// Deactivate B and try to remove
top_node = tree->top();
- box.check(top_node == node_b, "Top node should be node_b");
+ REQUIRE(top_node == node_b);
tree->deactivate(node_b, 16);
tree->remove(node_b);
- box.check(tree->find(5) == nullptr, "Node B should be removed");
+ REQUIRE(tree->find(5) == nullptr);
// Deactivate C and try to remove
top_node = tree->top();
- box.check(top_node == node_c, "Top node should be node_c");
+ REQUIRE(top_node == node_c);
tree->deactivate(node_c, 16);
tree->remove(node_c);
- box.check(tree->find(7) == nullptr, "Node C should be removed");
+ REQUIRE(tree->find(7) == nullptr);
delete tree;
}
@@ -459,11 +432,8 @@ REGRESSION_TEST(Http2DependencyTree_remove_1)(RegressionTest *t, int /* atype AT
* |
* C(7)
*/
-REGRESSION_TEST(Http2DependencyTree_remove_2)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_remove_2", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C");
@@ -475,26 +445,26 @@ REGRESSION_TEST(Http2DependencyTree_remove_2)(RegressionTest *t, int /* atype AT
// Activate, deactivate, and remove C
tree->activate(node_c);
- box.check(tree->top() == node_c, "Top node should be node_c");
+ REQUIRE(tree->top() == node_c);
tree->deactivate(node_c, 16384);
tree->remove(node_c);
// Activate, deactivate, and remove A
tree->activate(node_a);
- box.check(tree->top() == node_a, "Top node should be node_a");
+ REQUIRE(tree->top() == node_a);
tree->deactivate(node_a, 16384);
tree->remove(node_a);
// Activate, deactivate, and remove B
tree->activate(node_b);
- box.check(tree->top() == node_b, "Top node should be node_b");
+ REQUIRE(tree->top() == node_b);
tree->deactivate(node_b, 16384);
tree->remove(node_b);
- box.check(tree->top() == nullptr, "Top node should be nullptr");
- box.check(tree->find(3) == nullptr, "Tree should be empty");
- box.check(tree->find(5) == nullptr, "Tree should be empty");
- box.check(tree->find(7) == nullptr, "Tree should be empty");
+ REQUIRE(tree->top() == nullptr);
+ REQUIRE(tree->find(3) == nullptr);
+ REQUIRE(tree->find(5) == nullptr);
+ REQUIRE(tree->find(7) == nullptr);
delete tree;
}
@@ -508,11 +478,8 @@ REGRESSION_TEST(Http2DependencyTree_remove_2)(RegressionTest *t, int /* atype AT
* / \
* B C
*/
-REGRESSION_TEST(Http2DependencyTree_exclusive_node)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_exclusive_node", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C"), d("D");
@@ -526,7 +493,7 @@ REGRESSION_TEST(Http2DependencyTree_exclusive_node)(RegressionTest *t, int /* at
tree->deactivate(B, 0);
tree->remove(B);
- box.check(tree->top() == nullptr, "Tree top should be nullptr");
+ REQUIRE(tree->top() == nullptr);
delete tree;
}
@@ -540,11 +507,8 @@ REGRESSION_TEST(Http2DependencyTree_exclusive_node)(RegressionTest *t, int /* at
* C A
*
*/
-REGRESSION_TEST(Http2DependencyTree_reprioritize)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_reprioritize", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C");
@@ -561,7 +525,7 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize)(RegressionTest *t, int /* atyp
tree->deactivate(A, 0);
tree->remove(A);
- box.check(tree->top()->t != nullptr, "should not core dump");
+ REQUIRE(tree->top()->t != nullptr);
delete tree;
}
@@ -579,11 +543,8 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize)(RegressionTest *t, int /* atyp
* | |
* F E
*/
-REGRESSION_TEST(Http2DependencyTree_reprioritize_2)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_reprioritize_2", "[http2][Http2DependencyTree]")
{
- 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");
@@ -600,13 +561,13 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_2)(RegressionTest *t, int /* at
Node *node_d = tree->find(7);
tree->activate(node_b);
- box.check(node_x->queue->in(node_a->entry), "A should be in x's queue");
+ REQUIRE(node_x->queue->in(node_a->entry));
tree->reprioritize(1, 7, true);
- box.check(!node_x->queue->in(node_a->entry), "A should not be in x's queue");
- box.check(node_x->queue->in(node_d->entry), "D should be in x's queue");
- box.check(node_d->queue->in(node_a->entry), "A should be in d's queue");
+ REQUIRE(!node_x->queue->in(node_a->entry));
+ REQUIRE(node_x->queue->in(node_d->entry));
+ REQUIRE(node_d->queue->in(node_a->entry));
delete tree;
}
@@ -624,11 +585,8 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_2)(RegressionTest *t, int /* at
* | |
* F E
*/
-REGRESSION_TEST(Http2DependencyTree_reprioritize_3)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_reprioritize_3", "[http2][Http2DependencyTree]")
{
- 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");
@@ -648,11 +606,11 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_3)(RegressionTest *t, int /* at
tree->activate(node_f);
tree->reprioritize(1, 7, true);
- box.check(node_a->queue->in(node_f->entry), "F should be in A's queue");
- box.check(node_d->queue->in(node_a->entry), "A 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");
+ REQUIRE(node_a->queue->in(node_f->entry));
+ REQUIRE(node_d->queue->in(node_a->entry));
+ REQUIRE(node_x->queue->in(node_d->entry));
+ REQUIRE(!node_a->queue->in(node_c->entry));
+ REQUIRE(node_c->queue->empty());
delete tree;
}
@@ -671,11 +629,8 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_3)(RegressionTest *t, int /* at
* |
* F
*/
-REGRESSION_TEST(Http2DependencyTree_reprioritize_4)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_reprioritize_4", "[http2][Http2DependencyTree]")
{
- 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");
@@ -695,11 +650,11 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_4)(RegressionTest *t, int /* at
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");
+ REQUIRE(!node_a->queue->in(node_f->entry));
+ REQUIRE(node_d->queue->in(node_f->entry));
+ REQUIRE(node_x->queue->in(node_d->entry));
+ REQUIRE(!node_a->queue->in(node_c->entry));
+ REQUIRE(node_c->queue->empty());
delete tree;
}
@@ -718,11 +673,8 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_4)(RegressionTest *t, int /* at
* | |
* F F
*/
-REGRESSION_TEST(Http2DependencyTree_reprioritize_5)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_reprioritize_5", "[http2][Http2DependencyTree]")
{
- 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");
@@ -743,12 +695,12 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_5)(RegressionTest *t, int /* at
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");
+ REQUIRE(node_a->queue->in(node_b->entry));
+ REQUIRE(node_b->queue->in(node_d->entry));
+ REQUIRE(!node_c->queue->in(node_d->entry));
+ REQUIRE(node_x->queue->in(node_a->entry));
+ REQUIRE(!node_a->queue->in(node_c->entry));
+ REQUIRE(node_c->queue->empty());
delete tree;
}
@@ -769,11 +721,8 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_5)(RegressionTest *t, int /* at
* \
* C
*/
-REGRESSION_TEST(Http2DependencyTree_insert_with_empty_parent)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_insert_with_empty_parent", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C");
@@ -781,19 +730,19 @@ REGRESSION_TEST(Http2DependencyTree_insert_with_empty_parent)(RegressionTest *t,
Node *b_n = tree->add(9, 7, 30, true, &b);
- 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");
+ REQUIRE(b_n->parent->id == 9);
+ REQUIRE(tree->find(9) == nullptr);
+ REQUIRE(tree->find_shadow(9)->is_shadow() == true);
Node *c_n = tree->add(7, 11, 30, false, &c);
tree->remove(b_n);
- 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(9)->is_shadow() == true, "Nodes 9 should be existed after removing");
+ REQUIRE(c_n->parent->id == 9);
+ REQUIRE(tree->find(7) == nullptr);
+ REQUIRE(tree->find_shadow(9)->is_shadow() == true);
tree->remove(c_n);
- box.check(tree->find_shadow(9) == nullptr, "Shadow nodes should be remove");
+ REQUIRE(tree->find_shadow(9) == nullptr);
delete tree;
}
@@ -806,11 +755,8 @@ REGRESSION_TEST(Http2DependencyTree_insert_with_empty_parent)(RegressionTest *t,
* \ \
* B shadow
*/
-REGRESSION_TEST(Http2DependencyTree_shadow_reprioritize)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_shadow_reprioritize", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B");
@@ -818,10 +764,11 @@ REGRESSION_TEST(Http2DependencyTree_shadow_reprioritize)(RegressionTest *t, int
tree->add(9, 7, 30, true, &b);
Node *s_n = tree->find_shadow(9);
- box.check(s_n != nullptr && s_n->is_shadow() == true, "Shadow nodes should not be nullptr");
+ REQUIRE(s_n != nullptr);
+ REQUIRE(s_n->is_shadow() == true);
tree->reprioritize(s_n, 7, false);
- box.check(tree->find_shadow(9) == nullptr, "Shadow nodes should be nullptr after reprioritizing");
+ REQUIRE(tree->find_shadow(9) == nullptr);
delete tree;
}
@@ -838,11 +785,8 @@ REGRESSION_TEST(Http2DependencyTree_shadow_reprioritize)(RegressionTest *t, int
* |
* D
*/
-REGRESSION_TEST(Http2DependencyTree_delete_parent_before_child_arrives)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_delete_parent_before_child_arrives", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C"), d("D"), e("E");
@@ -853,7 +797,7 @@ REGRESSION_TEST(Http2DependencyTree_delete_parent_before_child_arrives)(Regressi
// 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");
+ REQUIRE(node_c->parent->id == 3);
// See if it remembers two missing ancestors
Node *node_d = tree->add(7, 9, 20, false, &d);
@@ -862,7 +806,7 @@ REGRESSION_TEST(Http2DependencyTree_delete_parent_before_child_arrives)(Regressi
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");
+ REQUIRE(node_e->parent->id == 3);
delete tree;
}
@@ -879,11 +823,8 @@ REGRESSION_TEST(Http2DependencyTree_delete_parent_before_child_arrives)(Regressi
* | |
* D D
*/
-REGRESSION_TEST(Http2DependencyTree_handle_priority_nodes)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_handle_priority_nodes", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C"), d("D"), e("E");
@@ -899,15 +840,15 @@ REGRESSION_TEST(Http2DependencyTree_handle_priority_nodes)(RegressionTest *t, in
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");
+ REQUIRE(node_a->parent->id == 3);
+ REQUIRE(node_b->parent->id == 5);
+ REQUIRE(node_c->parent->id == 7);
+ REQUIRE(node_d->parent->id == 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");
+ REQUIRE(node_p1 != nullptr);
delete tree;
}
@@ -923,11 +864,8 @@ REGRESSION_TEST(Http2DependencyTree_handle_priority_nodes)(RegressionTest *t, in
* |
* B
*/
-REGRESSION_TEST(Http2DependencyTree_reprioritize_shadow_node)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_reprioritize_shadow_node", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C");
@@ -939,27 +877,29 @@ REGRESSION_TEST(Http2DependencyTree_reprioritize_shadow_node)(RegressionTest *t,
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");
+ REQUIRE(b_n != nullptr);
+ REQUIRE(b_n->parent->id == 7);
+ REQUIRE(c_n == nullptr);
+ REQUIRE(c_shadow_n != nullptr);
+ REQUIRE(c_shadow_n->parent->id == 0);
// 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");
+ REQUIRE(c_n != nullptr);
+ REQUIRE(c_n->parent->id);
+ REQUIRE(c_n->weight == 30);
// 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");
+ REQUIRE(c_n != nullptr);
delete tree;
}
-REGRESSION_TEST(Http2DependencyTree_missing_parent)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_missing_parent", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A"), b("B"), c("C");
@@ -968,22 +908,23 @@ REGRESSION_TEST(Http2DependencyTree_missing_parent)(RegressionTest *t, int /* at
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");
+ REQUIRE(c_n == nullptr);
+ REQUIRE(c_shadow_n != nullptr);
+ REQUIRE(c_shadow_n->is_shadow() == true);
tree->add(0, 5, 15, false, &c);
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");
+ REQUIRE(c_n != nullptr);
+ REQUIRE(c_n->is_shadow() == false);
+ REQUIRE(c_n->point == 5);
+ REQUIRE(c_n->weight == 15);
delete tree;
}
-REGRESSION_TEST(Http2DependencyTree_max_depth)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+TEST_CASE("Http2DependencyTree_max_depth", "[http2][Http2DependencyTree]")
{
- TestBox box(t, pstatus);
- box = REGRESSION_TEST_PASSED;
-
Tree *tree = new Tree(100);
string a("A");
for (int i = 0; i < 100; ++i) {
@@ -991,17 +932,9 @@ REGRESSION_TEST(Http2DependencyTree_max_depth)(RegressionTest *t, int /* atype A
}
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");
+ REQUIRE(node->parent->id == 0);
+ REQUIRE(leaf != nullptr);
+ REQUIRE(leaf->parent->id != 0);
delete tree;
}
-
-int
-main(int /* argc ATS_UNUSED */, const char ** /* argv ATS_UNUSED */)
-{
- const char *name = "Http2DependencyTree";
- RegressionTest::run(name, REGRESSION_TEST_QUICK);
-
- return RegressionTest::final_status == REGRESSION_TEST_PASSED ? 0 : 1;
-}
[trafficserver] 01/02: HTTP/2 priority fixes to match common
browser patterns
Posted by bc...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
bcall pushed a commit to branch 8.0.x
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit 1e83131fac2e1ea95dde473c6e5cc801ae6b8594
Author: Susan Hinrichs <sh...@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)
---
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;
}