This is an automated email from the ASF dual-hosted git repository. sorber pushed a commit to branch 6.2.x in repository https://git-dual.apache.org/repos/asf/trafficserver.git
commit a5576c89da964902f55b6692f899c09b02cafc04 Author: Masaori Koshiba <[email protected]> AuthorDate: Thu Jul 28 20:06:09 2016 +0900 TS-4554: Add some limitations in Http2DependencyTree - Set max depth of Http2DependencyTree When the depth over the maximum, new node will be a children of root node. - Limit number of Http2DependencyTree node - Remove node from Http2DependencyTree when delete streams (cherry picked from commit c71fa8c5e4c4c80217e7927752fd6febb5812ba7) Conflicts: proxy/http2/Http2ConnectionState.cc --- proxy/http2/Http2ConnectionState.cc | 25 ++-- proxy/http2/Http2ConnectionState.h | 8 +- proxy/http2/Http2DependencyTree.h | 59 ++++++++- proxy/http2/test_Http2DependencyTree.cc | 211 ++++++++++++++++++++++++++++++-- 4 files changed, 277 insertions(+), 26 deletions(-) diff --git a/proxy/http2/Http2ConnectionState.cc b/proxy/http2/Http2ConnectionState.cc index a28b4b3..1d264fe 100644 --- a/proxy/http2/Http2ConnectionState.cc +++ b/proxy/http2/Http2ConnectionState.cc @@ -263,8 +263,9 @@ rcv_headers_frame(Http2ConnectionState &cstate, const Http2Frame &frame) if (node != NULL) { stream->priority_node = node; } else { - DebugHttp2Stream(cstate.ua_session, stream_id, "PRIORITY - dep: %d, weight: %d, excl: %d", params.priority.stream_dependency, - params.priority.weight, params.priority.exclusive_flag); + DebugHttp2Stream(cstate.ua_session, stream_id, "PRIORITY - dep: %d, weight: %d, excl: %d, tree size: %d", + params.priority.stream_dependency, params.priority.weight, params.priority.exclusive_flag, + cstate.dependency_tree->size()); stream->priority_node = cstate.dependency_tree->add(params.priority.stream_dependency, stream_id, params.priority.weight, params.priority.exclusive_flag, stream); @@ -358,8 +359,8 @@ rcv_priority_frame(Http2ConnectionState &cstate, const Http2Frame &frame) return Http2Error(HTTP2_ERROR_CLASS_CONNECTION, HTTP2_ERROR_PROTOCOL_ERROR); } - DebugHttp2Stream(cstate.ua_session, stream_id, "PRIORITY - dep: %d, weight: %d, excl: %d", priority.stream_dependency, - priority.weight, priority.exclusive_flag); + DebugHttp2Stream(cstate.ua_session, stream_id, "PRIORITY - dep: %d, weight: %d, excl: %d, tree size: %d", + priority.stream_dependency, priority.weight, priority.exclusive_flag, cstate.dependency_tree->size()); DependencyTree::Node *node = cstate.dependency_tree->find(stream_id); @@ -368,11 +369,12 @@ rcv_priority_frame(Http2ConnectionState &cstate, const Http2Frame &frame) DebugHttp2Stream(cstate.ua_session, stream_id, "Reprioritize"); cstate.dependency_tree->reprioritize(node, priority.stream_dependency, priority.exclusive_flag); } else { - cstate.dependency_tree->add(priority.stream_dependency, stream_id, priority.weight, priority.exclusive_flag, NULL); + // PRIORITY frame is received before HEADERS frame. - Http2Stream *stream = cstate.find_stream(stream_id); - if (stream != NULL) { - stream->priority_node = node; + // Restrict number of inactive node in dependency tree smaller than max_concurrent_streams. + // Current number of inactive node is size of tree minus active node count. + if (Http2::max_concurrent_streams_in > cstate.dependency_tree->size() - cstate.get_client_stream_count() + 1) { + cstate.dependency_tree->add(priority.stream_dependency, stream_id, priority.weight, priority.exclusive_flag, NULL); } } @@ -971,8 +973,11 @@ Http2ConnectionState::delete_stream(Http2Stream *stream) if (Http2::stream_priority_enabled) { DependencyTree::Node *node = stream->priority_node; - if (node != NULL && node->active) { - dependency_tree->deactivate(node, 0); + if (node != NULL) { + if (node->active) { + dependency_tree->deactivate(node, 0); + } + dependency_tree->remove(node); } } diff --git a/proxy/http2/Http2ConnectionState.h b/proxy/http2/Http2ConnectionState.h index 0475b33..14a00d6 100644 --- a/proxy/http2/Http2ConnectionState.h +++ b/proxy/http2/Http2ConnectionState.h @@ -146,7 +146,7 @@ public: continued_buffer.iov_base = NULL; continued_buffer.iov_len = 0; - dependency_tree = new DependencyTree(); + dependency_tree = new DependencyTree(Http2::max_concurrent_streams_in); } void @@ -200,6 +200,12 @@ public: continued_stream_id = 0; } + uint32_t + get_client_stream_count() const + { + return client_streams_count; + } + // Connection level window size ssize_t client_rwnd, server_rwnd; diff --git a/proxy/http2/Http2DependencyTree.h b/proxy/http2/Http2DependencyTree.h index 4e83cd0..8a16c13 100644 --- a/proxy/http2/Http2DependencyTree.h +++ b/proxy/http2/Http2DependencyTree.h @@ -34,7 +34,8 @@ #include "HTTP2.h" // TODO: K is a constant, 256 is temporal value. -const static int K = 256; +const static uint32_t K = 256; +const static uint32_t HTTP2_DEPENDENCY_TREE_MAX_DEPTH = 256; template <typename T> class Http2DependencyTree { @@ -104,40 +105,47 @@ public: T t; }; - Http2DependencyTree() { _root = new Node(); } + Http2DependencyTree(uint32_t max_concurrent_streams) + : _root(new Node()), _max_depth(MIN(max_concurrent_streams, HTTP2_DEPENDENCY_TREE_MAX_DEPTH)), _node_count(0) + { + } ~Http2DependencyTree() { delete _root; } Node *find(uint32_t id); Node *add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t); + 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); Node *top(); void activate(Node *node); void deactivate(Node *node, uint32_t sent); void update(Node *node, uint32_t sent); + uint32_t size() const; private: - Node *_find(Node *node, uint32_t id); + 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); Node *_root; + uint32_t _max_depth; + uint32_t _node_count; }; template <typename T> typename Http2DependencyTree<T>::Node * -Http2DependencyTree<T>::_find(Node *node, uint32_t id) +Http2DependencyTree<T>::_find(Node *node, uint32_t id, uint32_t depth) { if (node->id == id) { return node; } - if (node->children.empty()) { + if (node->children.empty() || depth >= _max_depth) { return NULL; } Node *result = NULL; for (Node *n = node->children.head; n; n = n->link.next) { - result = _find(n, id); + result = _find(n, id, ++depth); if (result != NULL) { break; } @@ -174,11 +182,43 @@ Http2DependencyTree<T>::add(uint32_t parent_id, uint32_t id, uint32_t weight, bo parent->children.push(node); + ++_node_count; return node; } template <typename T> void +Http2DependencyTree<T>::remove(Node *node) +{ + if (node == _root || node->active) { + return; + } + + Node *parent = node->parent; + parent->children.remove(node); + if (node->queued) { + parent->queue->erase(node->entry); + } + + // Push queue entries + while (!node->queue->empty()) { + parent->queue->push(node->queue->top()); + node->queue->pop(); + } + + // Push children + while (!node->children.empty()) { + Node *child = node->children.pop(); + parent->children.push(child); + child->parent = parent; + } + + --_node_count; + delete node; +} + +template <typename T> +void Http2DependencyTree<T>::reprioritize(uint32_t id, uint32_t new_parent_id, bool exclusive) { Node *node = find(id); @@ -305,4 +345,11 @@ Http2DependencyTree<T>::update(Node *node, uint32_t sent) } } +template <typename T> +uint32_t +Http2DependencyTree<T>::size() const +{ + return _node_count; +} + #endif // __HTTP2_DEP_TREE_H__ diff --git a/proxy/http2/test_Http2DependencyTree.cc b/proxy/http2/test_Http2DependencyTree.cc index c94c373..e7c079a 100644 --- a/proxy/http2/test_Http2DependencyTree.cc +++ b/proxy/http2/test_Http2DependencyTree.cc @@ -47,7 +47,7 @@ REGRESSION_TEST(Http2DependencyTree_1)(RegressionTest *t, int /* atype ATS_UNUSE TestBox box(t, pstatus); box = REGRESSION_TEST_PASSED; - Tree *tree = new Tree(); + Tree *tree = new Tree(100); string a("A"), b("B"), c("C"), d("D"); tree->add(0, 1, 0, false, &b); @@ -90,7 +90,7 @@ REGRESSION_TEST(Http2DependencyTree_2)(RegressionTest *t, int /* atype ATS_UNUSE TestBox box(t, pstatus); box = REGRESSION_TEST_PASSED; - Tree *tree = new Tree(); + 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); @@ -132,7 +132,7 @@ REGRESSION_TEST(Http2DependencyTree_3)(RegressionTest *t, int /* atype ATS_UNUSE TestBox box(t, pstatus); box = REGRESSION_TEST_PASSED; - Tree *tree = new Tree(); + 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); @@ -167,7 +167,7 @@ REGRESSION_TEST(Http2DependencyTree_4)(RegressionTest *t, int /* atype ATS_UNUSE TestBox box(t, pstatus); box = REGRESSION_TEST_PASSED; - Tree *tree = new Tree(); + Tree *tree = new Tree(100); string a("A"); tree->add(0, 1, 0, false, &a); @@ -198,7 +198,7 @@ REGRESSION_TEST(Http2DependencyTree_5)(RegressionTest *t, int /* atype ATS_UNUSE TestBox box(t, pstatus); box = REGRESSION_TEST_PASSED; - Tree *tree = new Tree(); + Tree *tree = new Tree(100); string a("A"), b("B"), c("C"); tree->add(0, 3, 15, false, &a); @@ -233,7 +233,7 @@ REGRESSION_TEST(Http2DependencyTree_6)(RegressionTest *t, int /* atype ATS_UNUSE TestBox box(t, pstatus); box = REGRESSION_TEST_PASSED; - Tree *tree = new Tree(); + Tree *tree = new Tree(100); string a("A"), b("B"), c("C"), d("D"); @@ -270,12 +270,12 @@ REGRESSION_TEST(Http2DependencyTree_6)(RegressionTest *t, int /* atype ATS_UNUSE * A(3) B(5) ... I(19) * */ -REGRESSION_TEST(Http2DependencyTree_7)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +REGRESSION_TEST(Http2DependencyTree_Chrome_50)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) { TestBox box(t, pstatus); box = REGRESSION_TEST_PASSED; - Tree *tree = new Tree(); + Tree *tree = new Tree(100); string a("A"), b("B"), c("C"), d("D"), e("E"), f("F"), g("G"), h("H"), i("I"); @@ -289,7 +289,7 @@ REGRESSION_TEST(Http2DependencyTree_7)(RegressionTest *t, int /* atype ATS_UNUSE Tree::Node *node_h = tree->add(0, 17, 146, false, &h); Tree::Node *node_i = tree->add(0, 19, 146, false, &i); - // Activate A and B + // Activate nodes from A to I tree->activate(node_a); tree->activate(node_b); tree->activate(node_c); @@ -317,6 +317,199 @@ REGRESSION_TEST(Http2DependencyTree_7)(RegressionTest *t, int /* atype ATS_UNUSE delete tree; } +/** + * Tree of Chrome 51 + * + * ROOT + * | + * A(3) + * | + * B(5) + * . + * . + * . + * I(19) + * + */ +REGRESSION_TEST(Http2DependencyTree_Chrome_51)(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"), g("G"), h("H"), i("I"); + + Tree::Node *node_a = tree->add(0, 3, 255, false, &a); + Tree::Node *node_b = tree->add(3, 5, 255, false, &b); + Tree::Node *node_c = tree->add(5, 7, 255, false, &c); + Tree::Node *node_d = tree->add(7, 9, 182, false, &d); + Tree::Node *node_e = tree->add(9, 11, 182, false, &e); + Tree::Node *node_f = tree->add(11, 13, 182, false, &f); + Tree::Node *node_g = tree->add(13, 15, 146, false, &g); + Tree::Node *node_h = tree->add(15, 17, 146, false, &h); + Tree::Node *node_i = tree->add(17, 19, 146, false, &i); + + // Activate nodes A, C, E, G, and I + tree->activate(node_a); + tree->activate(node_c); + tree->activate(node_e); + tree->activate(node_g); + tree->activate(node_i); + + ostringstream oss; + + for (int i = 0; i < 9; ++i) { + Tree::Node *node = tree->top(); + if (node != NULL) { + oss << node->t->c_str(); + + tree->deactivate(node, 16384); + tree->remove(node); + } + } + + // Activate nodes B, D, F, and H + tree->activate(node_b); + tree->activate(node_d); + tree->activate(node_f); + tree->activate(node_h); + + for (int i = 0; i < 9; ++i) { + Tree::Node *node = tree->top(); + if (node != NULL) { + oss << node->t->c_str(); + + tree->deactivate(node, 16384); + tree->remove(node); + } + } + + const string expect = "ACEGIBDFH"; + + box.check(oss.str() == expect, "\nExpect : %s\nActual : %s", expect.c_str(), oss.str().c_str()); + + delete tree; +} + +/** + * Removing Node from tree 1 + * + * ROOT + * | + * A(3) + * / \ + * B(5) C(7) + * + */ +REGRESSION_TEST(Http2DependencyTree_remove_1)(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"); + + // NOTE, weight is actual weight - 1 + Tree::Node *node_a = tree->add(0, 3, 30, false, &a); + Tree::Node *node_b = tree->add(3, 5, 20, false, &b); + Tree::Node *node_c = tree->add(3, 7, 10, false, &c); + + // Activate A, B, and C + tree->activate(node_a); + tree->activate(node_b); + tree->activate(node_c); + + Tree::Node *top_node = NULL; + + // Deactivate A and try to remove + top_node = tree->top(); + box.check(top_node == node_a, "Top node should be node_a"); + tree->deactivate(node_a, 16); + tree->remove(node_a); + box.check(tree->find(3) == NULL, "Node A should be removed"); + + // Deactivate B and try to remove + top_node = tree->top(); + box.check(top_node == node_b, "Top node should be node_b"); + tree->deactivate(node_b, 16); + tree->remove(node_b); + box.check(tree->find(5) == NULL, "Node B should be removed"); + + // Deactivate C and try to remove + top_node = tree->top(); + box.check(top_node == node_c, "Top node should be node_c"); + tree->deactivate(node_c, 16); + tree->remove(node_c); + box.check(tree->find(7) == NULL, "Node C should be removed"); +} + +/** + * Removing Node from tree 2 + * + * ROOT + * | + * A(3) + * | + * B(5) + * | + * C(7) + */ +REGRESSION_TEST(Http2DependencyTree_remove_2)(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"); + + // NOTE, weight is actual weight - 1 + Tree::Node *node_a = tree->add(0, 3, 20, false, &a); + Tree::Node *node_b = tree->add(3, 5, 10, false, &b); + Tree::Node *node_c = tree->add(5, 7, 10, false, &c); + + // Activate, deactivate, and remove C + tree->activate(node_c); + box.check(tree->top() == node_c, "Top node should be 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"); + 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"); + tree->deactivate(node_b, 16384); + tree->remove(node_b); + + box.check(tree->top() == NULL, "Top node should be NULL"); + box.check(tree->find(3) == NULL, "Tree should be empty"); + box.check(tree->find(5) == NULL, "Tree should be empty"); + box.check(tree->find(7) == NULL, "Tree should be empty"); +} + +REGRESSION_TEST(Http2DependencyTree_max_depth)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Tree *tree = new Tree(100); + string a("A"); + + for (int i = 0; i < 200; ++i) { + tree->add(i, i + 1, 16, false, &a); + } + + Tree::Node *node = tree->find(101); + box.check(node->parent->id == 0, "101st node should be child of root node"); +} + int main(int /* argc ATS_UNUSED */, const char ** /* argv ATS_UNUSED */) { -- To stop receiving notification emails like this one, please contact "[email protected]" <[email protected]>.
