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 <[email protected]> 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 "[email protected]" <[email protected]>.
