anirudh anirudh - 20 days ago 14
C++ Question

_M_ construct null not valid error when trying to implement multi threaded queue

I am trying to implement a priority queue using using a simple linear approach as explained in Art of Multiprocessor programming. I'm new to c++ and have difficulty troubleshooting.

I've implemented two template classes and am testing them using a simple test method. As I'm not able to pin point the error, I'm pasting all the three classes below for reference.

I know that

_M_ construct null not valid
comes when trying to construct a string using
nullptr
, but am not sure where I'm doing that.

The three classes created are given below:

bin.h



#include <mutex>
#include <deque>
#include <memory>
#include <iostream>
using namespace std;

namespace priority
{
template<typename T>
class Bin
{
private:
std::deque<T> v;
std::mutex m;
public:
Bin() {
}

Bin(const Bin &o) {

}

const Bin &operator=(const Bin &other) {
return *this;
}

void put(T item) {
std::lock_guard<std::mutex> lock(m);
v.push_back(item);
}

T *get() {
std::lock_guard<std::mutex> lock(m);
if (v.size() == 0) {
return nullptr;
}
else {
T val = v.front();
T *ptr_val = &(val);
v.pop_front();
return ptr_val;
}
}

bool isEmpty() {
std::lock_guard<std::mutex> lock(m);
return v.size() == 0;
}

};
}


SimpleLinear.h



#include <mutex>
#include <vector>
#include <memory>
#include "Bin.h"

namespace priority
{
template<typename T>
class SimpleLinear
{
private:
int range;
std::vector<Bin<T>> pqueue;
public:
SimpleLinear(int range){
this->range = range;

for (int i = 0; i < range; i++)
{
pqueue.push_back(Bin<T>());
}

}

void add(T item, int key) {
pqueue[key].put(item);
}

T removeMin() {
for (int i = 0; i < range; i++)
{
T *item = pqueue[i].get();
if (item != nullptr) {
return *item;
}
}
return nullptr;
}

};
}


test.cpp



#include <iostream>
#include <vector>
#include <thread>
#include <algorithm>
#include "SimpleLinear.h"
using namespace std;
using namespace priority;

void te(SimpleLinear<string> s, int thread_id) {

s.add("sundar"+to_string(thread_id), thread_id);
s.add("akshaya"+to_string(thread_id), 3);
s.add("anirudh"+to_string(thread_id), 1);
s.add("aaditya"+to_string(thread_id), 5);
cout << s.removeMin() << endl;
cout << s.removeMin() << endl;
cout << s.removeMin() << endl;

}


int main(int argc, char const *argv[])
{

SimpleLinear<string> s(100);
std::vector<std::thread> v;

for (int i = 0; i < 100; i++)
{
// if (i % 2 == 0)
v.push_back(thread(te, std::ref(s), i));
// else
// v.push_back(thread(t, std::ref(s), i));


}
for_each(v.begin(), v.end(), std::mem_fn(&std::thread::join));
return 0;
}


I'm getting the error:

terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_M_construct null not valid
terminate called recursively
terminate called recursively
terminate called recursively
Aborted (core dumped)

Answer

One reason it crashes is that in SimpleLinear<T>::removeMin when T is std::string, return nullptr constructs a string from nullptr. basic_string::_M_construct null not valid basically says that std::string(nullptr) was invoked.


Another reason it may crash is that get function returns a pointer to a local variable. Local variables get destroyed when the function returns. This leads to undefined behavior.

A fix:

bool get(T& result) {
    std::lock_guard<std::mutex> lock(m);
    if (v.empty()) 
        return false;
    result = v.front();
    v.pop_front();
    return true;
}

And invoke it like:

T removeMin() {
    T result;
    for(int i = 0; i < range; i++)
        if(pqueue[i].get(result))    
            break;
    return result;
}