This is an automated email from the ASF dual-hosted git repository. bcall pushed a commit to branch 7.0.x in repository https://git-dual.apache.org/repos/asf/trafficserver.git
commit 7db28a68d2482685c11a44331d14f2ee35374d9f 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) --- iocore/hostdb/P_RefCountCache.h | 1 - lib/ts/PriorityQueue.h | 17 ++++++---- lib/ts/test_PriorityQueue.cc | 75 +++++++++++++++++++++++++++++++++++++++++ 3 files changed, 86 insertions(+), 7 deletions(-) diff --git a/iocore/hostdb/P_RefCountCache.h b/iocore/hostdb/P_RefCountCache.h index 5f69a2a..833952d 100644 --- a/iocore/hostdb/P_RefCountCache.h +++ b/iocore/hostdb/P_RefCountCache.h @@ -293,7 +293,6 @@ RefCountCachePartition<C>::make_space_for(unsigned int size) // If the first item has expired, lets evict it, and then go around again if (top_item->node->meta.expiry_time < now) { this->erase(top_item->node->meta.key); - expiry_queue.pop(); } else { // if the first item isn't expired-- the rest won't be either (queue is sorted) return false; } 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 f1c041d..27a3258 100644 --- a/lib/ts/test_PriorityQueue.cc +++ b/lib/ts/test_PriorityQueue.cc @@ -384,4 +384,79 @@ 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; } -- To stop receiving notification emails like this one, please contact "[email protected]" <[email protected]>.
