trafficserver-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sor...@apache.org
Subject [trafficserver] 05/05: TS-4915: Crash from hostdb in PriorityQueueLess
Date Fri, 04 Nov 2016 14:44:33 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 ff5df2d51702baa184ea33b1e2a3ac384020b559
Author: Susan Hinrichs <shinrich@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" <commits@trafficserver.apache.org>.

Mime
View raw message