Project

General

Profile

Bug #6686

segfault in prioritized queue dequeue

Added by Noah Watkins over 10 years ago. Updated almost 10 years ago.

Status:
Resolved
Priority:
Normal
Assignee:
-
Category:
-
Target version:
-
% Done:

0%

Source:
other
Tags:
Backport:
Regression:
No
Severity:
3 - minor
Reviewed:
Affected Versions:
ceph-qa-suite:
Pull request ID:
Crash signature (v1):
Crash signature (v2):

Description

I've been hitting the following fault on OSX. At first I suspected a nasty bug mixing libc++ with libstdc++ on accident, but that doesn't appear to be the case, as I replaced PrioritizedQueue with a very basic implementation and the problems have disappeared.

frame #5: 0x0000000101d22d1e ceph-mon`handle_fatal_signal(signum=11) + 1118 at signal_handler.cc:64
frame #6: 0x00007fff8811f5aa libsystem_platform.dylib`_sigtramp + 26
frame #7: 0x0000000101b39822 ceph-mon`PrioritizedQueue<DispatchQueue::QueueItem, unsigned long long>::SubQueue::front() const + 34
frame #8: 0x0000000101b38479 ceph-mon`PrioritizedQueue<DispatchQueue::QueueItem, unsigned long long>::dequeue() + 409
frame #9: 0x0000000101b372fb ceph-mon`DispatchQueue::entry() + 219
frame #10: 0x0000000101b9c68d ceph-mon`DispatchQueue::DispatchThread::entry() + 13

The following patch uses a single queue, and does no priority ordering. This works fine, so it seems as though a bug is in the current code, but I've not yet found it.

diff --git a/src/common/PrioritizedQueue.h b/src/common/PrioritizedQueue.h
index ecd8395..c0e074c 100644
--- a/src/common/PrioritizedQueue.h
+++ b/src/common/PrioritizedQueue.h
@@ -224,6 +224,8 @@ class PrioritizedQueue {
     }
   }

+  std::map<K, std::list<T> > testq;
+
   public:
   PrioritizedQueue(unsigned max_per, unsigned min_c)
     : total_priority(0),
@@ -233,138 +235,73 @@ class PrioritizedQueue {

   unsigned length() {
     unsigned total = 0;
-    for (typename map<unsigned, SubQueue>::iterator i = queue.begin();
-        i != queue.end();
-        ++i) {
-      assert(i->second.length());
-      total += i->second.length();
-    }
-    for (typename map<unsigned, SubQueue>::iterator i = high_queue.begin();
-        i != high_queue.end();
-        ++i) {
-      assert(i->second.length());
-      total += i->second.length();
-    }
+    typename std::map<K, std::list<T> >::iterator it;
+    for (it = testq.begin(); it != testq.end(); it++)
+      total += it->second.size();
     return total;
   }

   template <class F>
     void remove_by_filter(F f, list<T> *removed = 0) {
-      for (typename map<unsigned, SubQueue>::iterator i = queue.begin();
-          i != queue.end();
-          ) {
-        unsigned priority = i->first;
-
-        i->second.remove_by_filter(f, removed);
-        if (i->second.empty()) {
-          ++i;
-          remove_queue(priority);
-        } else {
-          ++i;
+      typename std::map<K, std::list<T> >::iterator it;
+      if (removed) {
+        for (it = testq.begin(); it != testq.end(); it++) {
+          typename std::list<T>::iterator it2;
+          for (it2 = it->second.begin(); it2 != it->second.end(); it2++) {
+            if (f(*it2))
+              removed->push_back(*it2);
+          }
         }
       }
-      for (typename map<unsigned, SubQueue>::iterator i = high_queue.begin();
-          i != high_queue.end();
-          ) {
-        i->second.remove_by_filter(f, removed);
-        if (i->second.empty()) {
-          high_queue.erase(i++);
-        } else {
-          ++i;
+      for (it = testq.begin(); it != testq.end(); it++) {
+        typename std::list<T>::iterator it2;
+        for (it2 = it->second.begin(); it2 != it->second.end();) {
+          if (f(*it2))
+            it->second.erase(it2++);
+          else
+            ++it2;
         }
       }
     }

   void remove_by_class(K k, list<T> *out = 0) {
-    for (typename map<unsigned, SubQueue>::iterator i = queue.begin();
-        i != queue.end();
-        ) {
-      i->second.remove_by_class(k, out);
-      if (i->second.empty()) {
-        unsigned priority = i->first;
-        ++i;
-        remove_queue(priority);
-      } else {
-        ++i;
-      }
-    }
-    for (typename map<unsigned, SubQueue>::iterator i = high_queue.begin();
-        i != high_queue.end();
-        ) {
-      i->second.remove_by_class(k, out);
-      if (i->second.empty()) {
-        high_queue.erase(i++);
-      } else {
-        ++i;
-      }
-    }
+    std::list<T> temp;
+    temp.splice(temp.begin(), testq[k]);
+    if (out)
+      out->splice(out->end(), temp);
   }

   void enqueue_strict(K cl, unsigned priority, T item) {
-    high_queue[priority].enqueue(cl, 0, item);
+    testq[cl].push_back(item);
   }

   void enqueue_strict_front(K cl, unsigned priority, T item) {
-    high_queue[priority].enqueue_front(cl, 0, item);
+    testq[cl].push_back(item);
   }

   void enqueue(K cl, unsigned priority, unsigned cost, T item) {
-    if (cost < min_cost)
-      cost = min_cost;
-    create_queue(priority)->enqueue(cl, cost, item);
+    testq[cl].push_back(item);
   }

   void enqueue_front(K cl, unsigned priority, unsigned cost, T item) {
-    if (cost < min_cost)
-      cost = min_cost;
-    create_queue(priority)->enqueue_front(cl, cost, item);
+    testq[cl].push_back(item);
   }

   bool empty() {
-    assert(total_priority >= 0);
-    assert((total_priority == 0) || !(queue.empty()));
-    return queue.empty() && high_queue.empty();
+    return length() == 0;
   }

   T dequeue() {
     assert(!empty());
-
-    if (!(high_queue.empty())) {
-      T ret = high_queue.rbegin()->second.front().second;
-      high_queue.rbegin()->second.pop_front();
-      if (high_queue.rbegin()->second.empty())
-        high_queue.erase(high_queue.rbegin()->first);
-      return ret;
-    }
-
-    // if there are multiple buckets/subqueues with sufficient tokens,
-    // we behave like a strict priority queue among all subqueues that
-    // are eligible to run.
-    for (typename map<unsigned, SubQueue>::iterator i = queue.begin();
-        i != queue.end();
-        ++i) {
-      assert(!(i->second.empty()));
-      if (i->second.front().first < i->second.num_tokens()) {
-        T ret = i->second.front().second;
-        unsigned cost = i->second.front().first;
-        i->second.take_tokens(cost);
-        i->second.pop_front();
-        if (i->second.empty())
-          remove_queue(i->first);
-        distribute_tokens(cost);
+    typename std::map<K, std::list<T> >::iterator it;
+    for (it = testq.begin(); it != testq.end(); it++) {
+      if (!it->second.empty()) {
+        T ret = it->second.front();
+        it->second.pop_front();
         return ret;
       }
     }
-
-    // if no subqueues have sufficient tokens, we behave like a strict
-    // priority queue.
-    T ret = queue.rbegin()->second.front().second;
-    unsigned cost = queue.rbegin()->second.front().first;
-    queue.rbegin()->second.pop_front();
-    if (queue.rbegin()->second.empty())
-      remove_queue(queue.rbegin()->first);
-    distribute_tokens(cost);
-    return ret;
+    assert(0);
   }

   void dump(Formatter *f) const {

Associated revisions

Revision 44028983 (diff)
Added by Noah Watkins over 10 years ago

prio-q: initialize cur iterator

For new SubQueues `cur` is not intialized, so front/pop_front will freak
out. I honestly I have no idea how this hasn't been seen, but it was
being triggered frequently on OSX.

Fixes: #6686

Signed-off-by: Noah Watkins <>
Reviewed-by: Samuel Just <>

History

#1 Updated by Sage Weil almost 10 years ago

  • Status changed from New to Resolved

Also available in: Atom PDF