Actions
Bug #6686
closedsegfault in prioritized queue dequeue
Status:
Resolved
Priority:
Normal
Assignee:
-
Category:
-
Target version:
-
% Done:
0%
Source:
other
Tags:
Backport:
Regression:
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 {
Actions