[GitHub] trafficserver pull request #1088: TS-4915: Crash from hostdb in PriorityQueu...

[shinrich]

Github user shinrich closed the pull request at:

https://github.com/apache/trafficserver/pull/1088


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] trafficserver pull request #1088: TS-4915: Crash from hostdb in PriorityQueu...

[shinrich]

Github user shinrich commented on a diff in the pull request:

https://github.com/apache/trafficserver/pull/1088#discussion_r83086541
  
--- Diff: lib/ts/PriorityQueue.h ---
@@ -110,6 +110,12 @@ PriorityQueue::pop()
 return;
   }
 
+  // SKH - I suspect this assignment is not preserving entry indices 
correctly.
--- End diff --

Ok, with a short enough Vec I could exercise the problem.  Definitely an 
edge case for pop(), but we should go ahead and fix it.  New commit with the 
fix and a test.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] trafficserver pull request #1088: TS-4915: Crash from hostdb in PriorityQueu...

[shinrich]

Github user shinrich commented on a diff in the pull request:

https://github.com/apache/trafficserver/pull/1088#discussion_r83084441
  
--- Diff: lib/ts/PriorityQueue.h ---
@@ -110,6 +110,12 @@ PriorityQueue::pop()
 return;
   }
 
+  // SKH - I suspect this assignment is not preserving entry indices 
correctly.
--- End diff --

Actually, I think that pop() is almost always safe since the last entry is 
largest and the swaps in bubble_down will fix up the indices.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] trafficserver pull request #1088: TS-4915: Crash from hostdb in PriorityQueu...

[jpeach]

Github user jpeach commented on a diff in the pull request:

https://github.com/apache/trafficserver/pull/1088#discussion_r83048953
  
--- Diff: lib/ts/PriorityQueue.h ---
@@ -110,6 +110,12 @@ PriorityQueue::pop()
 return;
   }
 
+  // SKH - I suspect this assignment is not preserving entry indices 
correctly.
--- End diff --

Can we construct a test case that checks this invariant?


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] trafficserver pull request #1088: TS-4915: Crash from hostdb in PriorityQueu...

[shinrich]

Github user shinrich commented on a diff in the pull request:

https://github.com/apache/trafficserver/pull/1088#discussion_r82863899
  
--- Diff: lib/ts/PriorityQueue.h ---
@@ -110,6 +110,12 @@ PriorityQueue::pop()
 return;
   }
 
+  // SKH - I suspect this assignment is not preserving entry indices 
correctly.
--- End diff --

Ok.  Hopefully a transient comment anyway.  @masaori335 should be able to 
take a look and tell me whether this is a concern or not.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] trafficserver pull request #1088: TS-4915: Crash from hostdb in PriorityQueu...

[PSUdaemon]

Github user PSUdaemon commented on a diff in the pull request:

https://github.com/apache/trafficserver/pull/1088#discussion_r82852063
  
--- Diff: lib/ts/PriorityQueue.h ---
@@ -110,6 +110,12 @@ PriorityQueue::pop()
 return;
   }
 
+  // SKH - I suspect this assignment is not preserving entry indices 
correctly.
--- End diff --

No need to put your initials in the comment as `git blame` will tell us who 
added this if someone is curious.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] trafficserver pull request #1088: TS-4915: Crash from hostdb in PriorityQueu...

[bryancall]

Github user bryancall commented on a diff in the pull request:

https://github.com/apache/trafficserver/pull/1088#discussion_r82836137
  
--- Diff: lib/ts/PriorityQueue.h ---
@@ -123,11 +129,18 @@ PriorityQueue::erase(PriorityQueueEntry 
*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());
+  unsigned int 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);
+if (!empty()) {
--- End diff --

Wouldn't this always be true and why are we doing a bubble up it is is in 
sorted order.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] trafficserver pull request #1088: TS-4915: Crash from hostdb in PriorityQueu...

[bryancall]

Github user bryancall commented on a diff in the pull request:

https://github.com/apache/trafficserver/pull/1088#discussion_r82832753
  
--- Diff: lib/ts/PriorityQueue.h ---
@@ -123,11 +129,18 @@ PriorityQueue::erase(PriorityQueueEntry 
*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());
+  unsigned int original_index = entry->index;
--- End diff --

Should be a const uint32_t


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

[GitHub] trafficserver pull request #1088: TS-4915: Crash from hostdb in PriorityQueu...

[shinrich]

GitHub user shinrich opened a pull request:

https://github.com/apache/trafficserver/pull/1088

TS-4915: Crash from hostdb in PriorityQueueLess

These changes have been running on my production box since leaving work 
Monday night.  Will keep an eye on it.  Lower traffic overnight might not be 
stressing it sufficiently.

The main change was in PriorityQueueLess<>::erase.  The assignment of the 
end item to the erase point was not preserving the entry index.  So the 
assumption that entry->index is less than _v.length() was made invalid the next 
time around.  I think breaking this entry->index == _v index assignment can 
also harm the bubble_sorting logic.  I think PriorityQueueLess<>::pop also has 
a problem, but my work load was not triggering that function, so I didn't dive 
in there.

The other change was in RefCountCachePartition::make_space_for.  There 
was an extra pop which I believe was doubly removing an entry already removed 
in PriorityQueueLess::erase (called from RefCountCachePartition::erase).

You can merge this pull request into a Git repository by running:

$ git pull https://github.com/shinrich/trafficserver ts-4915-2

Alternatively you can review and apply these changes as the patch at:

https://github.com/apache/trafficserver/pull/1088.patch

To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

This closes #1088


commit 0898a59bc33d63d18997a66437c808acd2e7e073
Author: Susan Hinrichs 
Date:   2016-10-11T09:20:11Z

TS-4915: Crash from hostdb in PriorityQueueLess




---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---