trafficserver-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sor...@apache.org
Subject [trafficserver] 01/05: TS-4554: Add some limitations in Http2DependencyTree
Date Fri, 04 Nov 2016 14:44:29 GMT
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 <masaori@apache.org>
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
"commits@trafficserver.apache.org" <commits@trafficserver.apache.org>.

Mime
View raw message