You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by zw...@apache.org on 2017/08/16 16:50:14 UTC
[trafficserver] branch master updated: Fix the queue when
reprioritize
This is an automated email from the ASF dual-hosted git repository.
zwoop pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push:
new 7f3df8c Fix the queue when reprioritize
7f3df8c is described below
commit 7f3df8c2076f99afdc392abfe84925c05902ede9
Author: scw00 <sc...@apache.org>
AuthorDate: Sat Aug 5 11:10:52 2017 +0800
Fix the queue when reprioritize
---
lib/ts/PriorityQueue.h | 8 ++
proxy/http2/Http2DependencyTree.h | 29 ++++++++
proxy/http2/test_Http2DependencyTree.cc | 126 ++++++++++++++++++++++++++++++++
3 files changed, 163 insertions(+)
diff --git a/lib/ts/PriorityQueue.h b/lib/ts/PriorityQueue.h
index 8e27cb3..06ea052 100644
--- a/lib/ts/PriorityQueue.h
+++ b/lib/ts/PriorityQueue.h
@@ -48,6 +48,7 @@ public:
PriorityQueue() {}
~PriorityQueue() {}
bool empty();
+ bool in(PriorityQueueEntry<T> *entry);
PriorityQueueEntry<T> *top();
void pop();
void push(PriorityQueueEntry<T> *);
@@ -73,6 +74,13 @@ PriorityQueue<T, Comp>::dump() const
template <typename T, typename Comp>
bool
+PriorityQueue<T, Comp>::in(PriorityQueueEntry<T> *entry)
+{
+ return _v.in(entry) != NULL;
+}
+
+template <typename T, typename Comp>
+bool
PriorityQueue<T, Comp>::empty()
{
return _v.length() == 0;
diff --git a/proxy/http2/Http2DependencyTree.h b/proxy/http2/Http2DependencyTree.h
index 8ad7fb0..70aed80 100644
--- a/proxy/http2/Http2DependencyTree.h
+++ b/proxy/http2/Http2DependencyTree.h
@@ -250,6 +250,8 @@ Http2DependencyTree<T>::reprioritize(Node *node, uint32_t new_parent_id, bool ex
// Do nothing
return;
}
+ // should not change the root node
+ ink_assert(node->parent);
Node *new_parent = find(new_parent_id);
if (new_parent == NULL) {
@@ -264,11 +266,29 @@ template <typename T>
void
Http2DependencyTree<T>::_change_parent(Node *node, Node *new_parent, bool exclusive)
{
+ ink_release_assert(node->parent != NULL);
node->parent->children.remove(node);
+ if (node->queued) {
+ node->parent->queue->erase(node->entry);
+ node->queued = false;
+
+ Node *current = node->parent;
+ while (current->queue->empty() && !current->active && current->parent != NULL) {
+ current->parent->queue->erase(current->entry);
+ current->queued = false;
+ current = current->parent;
+ }
+ }
+
node->parent = NULL;
if (exclusive) {
while (Node *child = new_parent->children.pop()) {
+ if (child->queued) {
+ child->parent->queue->erase(child->entry);
+ node->queue->push(child->entry);
+ }
+
node->children.push(child);
child->parent = node;
}
@@ -276,6 +296,15 @@ Http2DependencyTree<T>::_change_parent(Node *node, Node *new_parent, bool exclus
new_parent->children.push(node);
node->parent = new_parent;
+
+ if (node->active || !node->queue->empty()) {
+ Node *current = node;
+ while (current->parent != NULL && !current->queued) {
+ current->parent->queue->push(current->entry);
+ current->queued = true;
+ current = current->parent;
+ }
+ }
}
template <typename T>
diff --git a/proxy/http2/test_Http2DependencyTree.cc b/proxy/http2/test_Http2DependencyTree.cc
index a147685..896cc89 100644
--- a/proxy/http2/test_Http2DependencyTree.cc
+++ b/proxy/http2/test_Http2DependencyTree.cc
@@ -530,6 +530,132 @@ REGRESSION_TEST(Http2DependencyTree_exclusive_node)(RegressionTest *t, int /* at
delete tree;
}
+/** test for reprioritize with active node
+*
+* root root root
+* / \ / \ (remove A) / \
+* A B =======> C B =======> C B
+* \ /
+* C A
+*
+*/
+REGRESSION_TEST(Http2DependencyTree_reprioritize)(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::Node *A = tree->add(0, 7, 70, false, &a);
+ Tree::Node *B = tree->add(0, 3, 10, false, &b);
+ Tree::Node *C = tree->add(3, 5, 30, false, &c);
+
+ tree->activate(A);
+ tree->activate(B);
+ tree->activate(C);
+
+ tree->reprioritize(A, 5, false);
+
+ tree->deactivate(A, 0);
+ tree->remove(A);
+
+ box.check(tree->top()->t != nullptr, "should not core dump");
+
+ delete tree;
+}
+
+/**
+ * Reprioritization (exclusive)
+ *
+ * x x
+ * | |
+ * A D
+ * / \ |
+ * B C ==> A
+ * / \ /|\
+ * D E B C F
+ * | |
+ * F E
+ */
+REGRESSION_TEST(Http2DependencyTree_reprioritize_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"), 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);
+
+ Tree::Node *node_x = tree->find(0);
+ Tree::Node *node_a = tree->find(1);
+ Tree::Node *node_b = tree->find(3);
+ Tree::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");
+
+ 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");
+
+ delete tree;
+}
+
+/**
+ * Reprioritization (exclusive)
+ *
+ * x x
+ * | |
+ * A D
+ * / \ |
+ * B C ==> A
+ * / \ /|\
+ * D E B C F
+ * | |
+ * F E
+ */
+REGRESSION_TEST(Http2DependencyTree_reprioritize_3)(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);
+
+ Tree::Node *node_x = tree->find(0);
+ Tree::Node *node_a = tree->find(1);
+ Tree::Node *node_c = tree->find(5);
+ Tree::Node *node_d = tree->find(7);
+ Tree::Node *node_f = tree->find(11);
+
+ 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");
+
+ delete tree;
+}
+
REGRESSION_TEST(Http2DependencyTree_max_depth)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
{
TestBox box(t, pstatus);
--
To stop receiving notification emails like this one, please contact
['"commits@trafficserver.apache.org" <co...@trafficserver.apache.org>'].