You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by so...@apache.org on 2016/11/04 14:44:28 UTC
[trafficserver] branch 6.2.x updated (7109da3 -> ff5df2d)
This is an automated email from the ASF dual-hosted git repository.
sorber pushed a change to branch 6.2.x
in repository https://git-dual.apache.org/repos/asf/trafficserver.git.
from 7109da3 TS-4724: Added new server_request APIs to set/get host name and scheme in ts-lua plugin.
new a5576c8 TS-4554: Add some limitations in Http2DependencyTree
new 921d2cb TS-4537 Add `erase` method to PriorityQueue (#708)
new 94eeefa TS-4605: fix Coverity issue 1357058
new 2f45e75 TS-4953: Memory leaks in priority queue test
new ff5df2d TS-4915: Crash from hostdb in PriorityQueueLess
The 5 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "adds" were already present in the repository and have only
been added to this reference.
Summary of changes:
lib/ts/PriorityQueue.h | 27 +++-
lib/ts/test_PriorityQueue.cc | 183 +++++++++++++++++++++++++++
proxy/http2/Http2ConnectionState.cc | 25 ++--
proxy/http2/Http2ConnectionState.h | 8 +-
proxy/http2/Http2DependencyTree.h | 59 ++++++++-
proxy/http2/test_Http2DependencyTree.cc | 211 ++++++++++++++++++++++++++++++--
6 files changed, 485 insertions(+), 28 deletions(-)
--
To stop receiving notification emails like this one, please contact
['"commits@trafficserver.apache.org" <co...@trafficserver.apache.org>'].
[trafficserver] 05/05: TS-4915: Crash from hostdb in
PriorityQueueLess
Posted by so...@apache.org.
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 ff5df2d51702baa184ea33b1e2a3ac384020b559
Author: Susan Hinrichs <sh...@ieee.org>
AuthorDate: Tue Oct 11 09:20:11 2016 +0000
TS-4915: Crash from hostdb in PriorityQueueLess
(cherry picked from commit b19348c807d535192cb5059f86fbb0534d5df344)
Conflicts:
iocore/hostdb/P_RefCountCache.h
---
lib/ts/PriorityQueue.h | 17 ++++++----
lib/ts/test_PriorityQueue.cc | 75 ++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 86 insertions(+), 6 deletions(-)
diff --git a/lib/ts/PriorityQueue.h b/lib/ts/PriorityQueue.h
index e7fc21a..afae433 100644
--- a/lib/ts/PriorityQueue.h
+++ b/lib/ts/PriorityQueue.h
@@ -110,7 +110,7 @@ PriorityQueue<T, Comp>::pop()
return;
}
- _v[0] = _v[_v.length() - 1];
+ _swap(0, _v.length() - 1);
_v.pop();
_bubble_down(0);
}
@@ -123,11 +123,16 @@ PriorityQueue<T, Comp>::erase(PriorityQueueEntry<T> *entry)
return;
}
- _v[entry->index] = _v[_v.length() - 1];
- _v.pop();
- _bubble_down(entry->index);
- if (!empty()) {
- _bubble_up(entry->index);
+ ink_release_assert(entry->index < _v.length());
+ const uint32_t original_index = entry->index;
+ if (original_index != (_v.length() - 1)) {
+ // Move the erased item to the end to be popped off
+ _swap(original_index, _v.length() - 1);
+ _v.pop();
+ _bubble_down(original_index);
+ _bubble_up(original_index);
+ } else { // Otherwise, we are already at the end, just pop
+ _v.pop();
}
}
diff --git a/lib/ts/test_PriorityQueue.cc b/lib/ts/test_PriorityQueue.cc
index dd3f06f..4007078 100644
--- a/lib/ts/test_PriorityQueue.cc
+++ b/lib/ts/test_PriorityQueue.cc
@@ -384,6 +384,81 @@ REGRESSION_TEST(PriorityQueue_6)(RegressionTest *t, int /* atype ATS_UNUSED */,
delete entry_a;
delete entry_b;
delete entry_c;
+
+ PQ *pq2 = new PQ();
+
+ N *w = new N(10, "W");
+ N *x = new N(20, "X");
+ N *y = new N(30, "Y");
+ N *z = new N(40, "Z");
+
+ Entry *entry_w = new Entry(w);
+ Entry *entry_x = new Entry(x);
+ Entry *entry_y = new Entry(y);
+ Entry *entry_z = new Entry(z);
+
+ pq2->push(entry_z);
+ pq2->push(entry_y);
+ pq2->push(entry_x);
+ pq2->push(entry_w);
+
+ box.check(pq2->top() == entry_w, "top should be entry_w 1");
+ pq2->erase(entry_x);
+ box.check(pq2->top() == entry_w, "top should be entry_w 2");
+ // The following two cases should test that erase preserves the index
+ pq2->erase(entry_y);
+ box.check(pq2->top() == entry_w, "top should be entry_w 3");
+ pq2->erase(entry_z);
+ box.check(pq2->top() == entry_w, "top should be entry_w 4");
+
+ delete pq2;
+
+ delete w;
+ delete x;
+ delete y;
+ delete z;
+
+ delete entry_w;
+ delete entry_x;
+ delete entry_y;
+ delete entry_z;
+}
+
+// Test erase and pop method to ensure the index entries are updated (TS-4915)
+REGRESSION_TEST(PriorityQueue_7)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+{
+ TestBox box(t, pstatus);
+ box = REGRESSION_TEST_PASSED;
+
+ PQ *pq2 = new PQ();
+
+ N *x = new N(20, "X");
+ N *y = new N(30, "Y");
+ N *z = new N(40, "Z");
+
+ Entry *entry_x = new Entry(x);
+ Entry *entry_y = new Entry(y);
+ Entry *entry_z = new Entry(z);
+
+ pq2->push(entry_z);
+ pq2->push(entry_y);
+ pq2->push(entry_x);
+
+ box.check(pq2->top() == entry_x, "top should be entry_x");
+ pq2->pop();
+ box.check(pq2->top() == entry_y, "top should be entry_y");
+ pq2->erase(entry_y);
+ box.check(pq2->top() == entry_z, "top should be entry_z");
+
+ delete pq2;
+
+ delete x;
+ delete y;
+ delete z;
+
+ delete entry_x;
+ delete entry_y;
+ delete entry_z;
}
int
--
To stop receiving notification emails like this one, please contact
"commits@trafficserver.apache.org" <co...@trafficserver.apache.org>.
[trafficserver] 01/05: TS-4554: Add some limitations in
Http2DependencyTree
Posted by so...@apache.org.
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 <ma...@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" <co...@trafficserver.apache.org>.
[trafficserver] 04/05: TS-4953: Memory leaks in priority queue test
Posted by so...@apache.org.
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 2f45e75a9936d08b4a2d6bf65d20f39294d1163d
Author: Bryan Call <bc...@apache.org>
AuthorDate: Tue Oct 11 10:49:48 2016 -0700
TS-4953: Memory leaks in priority queue test
(cherry picked from commit 5b1901410e04ff76a8e508b848c7a6cd53175a07)
---
lib/ts/test_PriorityQueue.cc | 78 ++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 78 insertions(+)
diff --git a/lib/ts/test_PriorityQueue.cc b/lib/ts/test_PriorityQueue.cc
index 807e000..dd3f06f 100644
--- a/lib/ts/test_PriorityQueue.cc
+++ b/lib/ts/test_PriorityQueue.cc
@@ -74,6 +74,10 @@ REGRESSION_TEST(PriorityQueue_1)(RegressionTest *t, int /* atype ATS_UNUSED */,
pq->pop();
box.check(pq->top() == NULL, "top should be NULL");
+
+ delete pq;
+ delete a;
+ delete entry_a;
}
// Increase weight
@@ -107,6 +111,16 @@ REGRESSION_TEST(PriorityQueue_2)(RegressionTest *t, int /* atype ATS_UNUSED */,
pq->update(entry_b, true);
box.check(pq->top() == entry_c, "top should be entry_c");
+
+ delete pq;
+
+ delete a;
+ delete b;
+ delete c;
+
+ delete entry_a;
+ delete entry_b;
+ delete entry_c;
}
// Decrease weight
@@ -140,6 +154,16 @@ REGRESSION_TEST(PriorityQueue_3)(RegressionTest *t, int /* atype ATS_UNUSED */,
pq->update(entry_c, false);
box.check(pq->top() == entry_c, "top should be entry_c");
+
+ delete pq;
+
+ delete a;
+ delete b;
+ delete c;
+
+ delete entry_a;
+ delete entry_b;
+ delete entry_c;
}
// Push, top, and pop 9 entries
@@ -200,6 +224,28 @@ REGRESSION_TEST(PriorityQueue_4)(RegressionTest *t, int /* atype ATS_UNUSED */,
pq->pop();
box.check(pq->top() == NULL, "top should be NULL");
+
+ delete pq;
+
+ delete a;
+ delete b;
+ delete c;
+ delete d;
+ delete e;
+ delete f;
+ delete g;
+ delete h;
+ delete i;
+
+ delete entry_a;
+ delete entry_b;
+ delete entry_c;
+ delete entry_d;
+ delete entry_e;
+ delete entry_f;
+ delete entry_g;
+ delete entry_h;
+ delete entry_i;
}
// // Push, top, pop, and update 9 entries
@@ -276,6 +322,28 @@ REGRESSION_TEST(PriorityQueue_5)(RegressionTest *t, int /* atype ATS_UNUSED */,
pq->pop();
box.check(pq->top() == NULL, "top should be NULL");
+
+ delete pq;
+
+ delete a;
+ delete b;
+ delete c;
+ delete d;
+ delete e;
+ delete f;
+ delete g;
+ delete h;
+ delete i;
+
+ delete entry_a;
+ delete entry_b;
+ delete entry_c;
+ delete entry_d;
+ delete entry_e;
+ delete entry_f;
+ delete entry_g;
+ delete entry_h;
+ delete entry_i;
}
// Test erase method
@@ -306,6 +374,16 @@ REGRESSION_TEST(PriorityQueue_6)(RegressionTest *t, int /* atype ATS_UNUSED */,
pq->erase(entry_b);
box.check(pq->top() == NULL, "top should be NULL");
box.check(pq->empty(), "should be empty");
+
+ delete pq;
+
+ delete a;
+ delete b;
+ delete c;
+
+ delete entry_a;
+ delete entry_b;
+ delete entry_c;
}
int
--
To stop receiving notification emails like this one, please contact
"commits@trafficserver.apache.org" <co...@trafficserver.apache.org>.
[trafficserver] 02/05: TS-4537 Add `erase` method to PriorityQueue
(#708)
Posted by so...@apache.org.
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 921d2cb24f74bdc937df7c03406c26a841fe6bfc
Author: Thomas Jackson <ja...@gmail.com>
AuthorDate: Tue Jun 14 23:05:04 2016 -0700
TS-4537 Add `erase` method to PriorityQueue (#708)
This closes #708
(cherry picked from commit 78850a89e62c095438a1e7a1c4a25da69b446a4b)
Conflicts:
lib/ts/test_PriorityQueue.cc
---
lib/ts/PriorityQueue.h | 20 +++++++++++++++++++-
lib/ts/test_PriorityQueue.cc | 30 ++++++++++++++++++++++++++++++
2 files changed, 49 insertions(+), 1 deletion(-)
diff --git a/lib/ts/PriorityQueue.h b/lib/ts/PriorityQueue.h
index 109f7d4..6b9f821 100644
--- a/lib/ts/PriorityQueue.h
+++ b/lib/ts/PriorityQueue.h
@@ -28,7 +28,8 @@
#include "ts/Vec.h"
template <typename T> struct PriorityQueueEntry {
- PriorityQueueEntry(T n) : index(0), node(n) {}
+ PriorityQueueEntry(T n) : index(0), node(n){};
+ PriorityQueueEntry() : index(0){};
uint32_t index;
T node;
};
@@ -52,6 +53,7 @@ public:
void push(PriorityQueueEntry<T> *);
void update(PriorityQueueEntry<T> *);
void update(PriorityQueueEntry<T> *, bool);
+ void erase(PriorityQueueEntry<T> *);
const Vec<PriorityQueueEntry<T> *> &dump() const;
private:
@@ -115,6 +117,22 @@ PriorityQueue<T, Comp>::pop()
template <typename T, typename Comp>
void
+PriorityQueue<T, Comp>::erase(PriorityQueueEntry<T> *entry)
+{
+ if (empty()) {
+ return;
+ }
+
+ _v[entry->index] = _v[_v.length() - 1];
+ _v.pop();
+ _bubble_down(entry->index);
+ if (!empty()) {
+ _bubble_up(entry->index);
+ }
+}
+
+template <typename T, typename Comp>
+void
PriorityQueue<T, Comp>::update(PriorityQueueEntry<T> *entry)
{
ink_release_assert(entry != NULL);
diff --git a/lib/ts/test_PriorityQueue.cc b/lib/ts/test_PriorityQueue.cc
index 3ade64b..807e000 100644
--- a/lib/ts/test_PriorityQueue.cc
+++ b/lib/ts/test_PriorityQueue.cc
@@ -278,6 +278,36 @@ REGRESSION_TEST(PriorityQueue_5)(RegressionTest *t, int /* atype ATS_UNUSED */,
box.check(pq->top() == NULL, "top should be NULL");
}
+// Test erase method
+REGRESSION_TEST(PriorityQueue_6)(RegressionTest *t, int /* atype ATS_UNUSED */, int *pstatus)
+{
+ TestBox box(t, pstatus);
+ box = REGRESSION_TEST_PASSED;
+
+ PQ *pq = new PQ();
+
+ N *a = new N(10, "A");
+ N *b = new N(20, "B");
+ N *c = new N(30, "C");
+
+ Entry *entry_a = new Entry(a);
+ Entry *entry_b = new Entry(b);
+ Entry *entry_c = new Entry(c);
+
+ pq->push(entry_a);
+ pq->push(entry_b);
+ pq->push(entry_c);
+
+ box.check(pq->top() == entry_a, "top should be entry_a");
+ pq->erase(entry_a);
+ box.check(pq->top() == entry_b, "top should be entry_b");
+ pq->erase(entry_c);
+ box.check(pq->top() == entry_b, "top should be entry_b");
+ pq->erase(entry_b);
+ box.check(pq->top() == NULL, "top should be NULL");
+ box.check(pq->empty(), "should be empty");
+}
+
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" <co...@trafficserver.apache.org>.
[trafficserver] 03/05: TS-4605: fix Coverity issue 1357058
Posted by so...@apache.org.
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 94eeefa1518fe06f50fe4df2efdf79eef70940fc
Author: Masaori Koshiba <ma...@apache.org>
AuthorDate: Wed Jun 29 14:08:41 2016 +0900
TS-4605: fix Coverity issue 1357058
(cherry picked from commit e1a37058fc14646f517c304b6d277c788a9c0462)
---
lib/ts/PriorityQueue.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/lib/ts/PriorityQueue.h b/lib/ts/PriorityQueue.h
index 6b9f821..e7fc21a 100644
--- a/lib/ts/PriorityQueue.h
+++ b/lib/ts/PriorityQueue.h
@@ -29,7 +29,7 @@
template <typename T> struct PriorityQueueEntry {
PriorityQueueEntry(T n) : index(0), node(n){};
- PriorityQueueEntry() : index(0){};
+ PriorityQueueEntry() : index(0), node(NULL){};
uint32_t index;
T node;
};
--
To stop receiving notification emails like this one, please contact
"commits@trafficserver.apache.org" <co...@trafficserver.apache.org>.