Dereferecing a private variable unordered_map whose key is a custom struct in a class leads to a seg fault

Question

I'm working on a mini project where I'm implementing the Matrix Chain Multiplication.My implementation is building a tree where the nodes are defined as

struct Node
{
   char* seq;
   Node* left;
   Node* right;
};

where seq is a sequence of numbers to indicate the chain of matrices to compute. Another part is having a struct called matrix defined as

struct matrix
{
   std::tuple<int, int> dimension;
   std::vector<std::vector<int>> values;
};

where I use a 2D vector to store values.

The overall idea is I'll create a dictionary where its {"char" : matrix} where the char is a numerical value and store this dictionary into a class.

The following code snippet shows me creating the matrices

matrix *A1 = new matrix;
matrix *A2 = new matrix;
A1->dimension = std::make_tuple(4,10);
A2->dimension = std::make_tuple(10,3);

setValues(A1, 1);
setValues(A2, 2);

Node *n = new Node;
n->left = nullptr;
n->right = nullptr;
n->seq = static_cast<char*>(malloc(3 * sizeof(char)));
n->seq[0] = '0' + 1;
n->seq[1] = '0' + 2;
n->seq[2] = '\0';

where setValue is defined as

void setValues(matrix *x,int value)
{
   int row = std::get<0>(x->dimension);
   int col = std::get<1>(x->dimension);
   x->values.resize(row);
   for (int i = 0; i < row; ++i) 
   {
      x->values[i].resize(col);
   }
   for(int i = 0; i < row; i++)
   {
      for(int j = 0; j < col; j++)
      {
         x->values[i][j] = value;
      }
   }
}

I then create an unordered map of <char, matrix*>

std::unordered_map<char, matrix*> dict;
dict['1'] = A1;
dict['2'] = A2;

After this I call my constructor function for the class Sequence which is defined as

class Sequence
{
private:
    Node root;
    std::vector<std::vector<int>> s_table;
    std::unordered_map<char,matrix*> str_matrix_dict;
public:
    Sequence(std::vector<std::vector<int>> temp_table, std::unordered_map<char,matrix*> &str_matrix_dict);
    matrix* compute(Node* n);
}
   

where the constructor is defined as

Sequence::Sequence(
std::vector<std::vector<int>> temp_table,
std::unordered_map<char,matrix*> &temp_dict) : s_table(temp_table), str_matrix_dict(temp_dict)
{

and call the constructor like

 Sequence seq(s_table, dict);

where s_table is a 2d vector. Where my issue is inside of one of the class function called compute(Node* n) and defined as followed

matrix* Sequence::compute(Node* n)
{
/*
    code before
*/
if(n->left == nullptr && n->right == nullptr && n->seq[2] == '\0')
{
    matrix* matrix_A = str_matrix_dict[n->seq[0]];
    matrix* matrix_B = str_matrix_dict[n->seq[1]];
    matrix* matrix_C = new matrix;
    int m = std::get<0>(matrix_A->dimension);
    int n = std::get<1>(matrix_B->dimension);
    int z = std::get<1>(matrix_A->dimension);
    matrix_C->dimension = std::make_tuple(m,n);
    matrix_C->values.resize(m);
    for (int i = 0; i < m; ++i) 
    {
        matrix_C->values[i].resize(n);
    }
    matrix_mult(matrix_A,matrix_B,matrix_C,m,n,x);
    return matrix_C;
}
matrix* left_res = compute(n->left);
matrix* right_res = compute(n->right);
//code after (same computation as above)

The idea is recursively go through the binary tree and computing each side of a node matrice and returning it to the parent node to compute.

I get a seg fault in matrix_mult which is defined as

void Sequence::matrix_mult(matrix *a, matrix *b, matrix *c, int x, int y, int z)
{
std::cout << "calculating " << std::endl;
for(int row = 0; row < x; x++)
{
    for(int col = 0; row < y; y++)
    {
        for(int k = 0; k < z; k++)
        {
            c->values[row][col] += (a->values[row][k] * b->values[k][col]);
        }
    }
}

}

I seg fault on the 1st pass of the triple for loop. Inside of 'compute' when I try to print out values of the matrices I get no values. I'm guessing it has to do with how I'm passing by reference and dereferencing but not exactly sure. Reason I'm using pointers is I heard it's good practice to pass matrices by reference as it saves space and time rather than passing by value especially when working with very large matrices. I thought it would be straight forward on storing the matrices in a dictionary then store the dictionary in the class private variable to access within the function compute(which is a class function). Thank you for any advice/guidance.

This is also my compiler. I'm using nvcc as a part of this mini project is to incorporate gpu computation.

CXX = nvcc
CPP = gcc
CFLAGS = -std=c++11 -g
LDFLAGS =  -lcudart -lcudadevrt

main: main.o sequence.o
$(CXX) $(CFLAGS) -o main main.o sequence.o $(LDFLAGS)

main.o: main.cu
    $(CXX) $(CFLAGS) -c main.cu
sequence.o: sequence.cpp
    $(CXX) $(CFLAGS) -c sequence.cpp

clean:
    rm -f main main.o sequence.o

Answer 1

The way you provided the code makes it diffcult to pinpoint the issue, but the matrix_mult function clearly has some potential issues:

void Sequence::matrix_mult(matrix *a, matrix *b, matrix *c, int x, int y, int z)
{
std::cout << "calculating " << std::endl;
for(int row = 0; row < x; x++)
{
    for(int col = 0; row < y; y++)
    {
        for(int k = 0; k < z; k++)
        {
            c->values[row][col] += (a->values[row][k] * b->values[k][col]);
        }
    }
}

In the first loop, you are checking that row is less than x, then you are incrementing x instead of row. This will causes an infinite loop if the initial value of x is >= 0

The same issue applies to the second loop, the one iterating over y.

Finally, and this is just an observation, there is only one possible cause of segfault in that function, and that is an access to a matrix index that is out of bound. Since row and col are always 0, I would guess that at some point you are accessing a->values[0][k] or b->values[k][0] with a k that is out of range.

You can get detailed information on the cause of your segfault if you compile your code using gcc, and the flags -fsanitize=address -g3. You can find more informations here https://www.cse.unsw.edu.au/%7Elearn/debugging/modules/asan/

---

Answer 2

This is how I would approach the matrix class based on my comments. Online demo here : https://onlinegdb.com/TsJqqW9bP

#include <cassert>
#include <vector>
#include <iostream>

class int_matrix_t final // final matrix is not intended to be inherited from
{
public:
    // use std::size_t for sizes and indexes (this is what the standard library does too)
    inline int_matrix_t(std::size_t rows, std::size_t cols) :
        m_rows{rows}, 
        m_cols{cols}, 
        m_data(rows*cols,0) // allocate memory for the matrix and set all values to 0
    {
        // one of the responsibilities of classes
        // is to make sure that the invariants are always satisfied
        // double check this for debug builds.
        assert(m_rows > 0);
        assert(m_cols > 0);
    }

    // A constructor that takes a 2D array and initializes the matrix with it
    // a template is used for ease of use see construction of matrices in main
    template<typename std::size_t rows_v, typename std::size_t cols_v>
    int_matrix_t(const int (&data)[rows_v][cols_v]) : m_rows{rows_v}, m_cols{cols_v}, m_data(rows_v*cols_v)
    {
        // copy data from the 2D array to the matrix
        for(std::size_t row{0ul}; row < rows_v; ++row)
        {
            for(std::size_t col{0ul}; col < cols_v; ++col)
            {
                at(row,col) = data[row][col];
            }
        }
    }

    // copy/move constructors will be generated by the compiler
    // which is fine because members are all copyable and movable

    ~int_matrix_t() = default;

    
    // pass right hand side matrix as const reference to avoid copying
    // and to make sure it is not modified by the multiplication operator
    // also the multiplication operator is const, it should not modify this instance (this is a design choice, inplace multiplication is also an option)
    inline int_matrix_t operator*(const int_matrix_t& rhs) const
    {
        assert( m_rows == rhs.m_rows);    
        assert( m_cols == rhs.m_rows);

        int_matrix_t result{m_rows, m_cols};
        for(std::size_t row{0ul}; row < m_rows; ++row)
        {
            for(std::size_t col{0ul}; col < rhs.m_cols; ++col)
            {
                int sum{};
                for(std::size_t k{0ul}; k < m_cols; ++k)
                {
                    sum += at(row,k) * rhs.at(k,col);
                }
                result.m_data[row*rhs.m_cols + col] = sum;
            }
        }
        return result;
    }

    // since the memory is contiguous we need to provide a way to access the elements
    // by row and column

    inline int& at(std::size_t row, std::size_t col)
    {
        return m_data[row*m_cols + col];
    }

    inline int at(std::size_t row, std::size_t col) const
    {
        return m_data[row*m_cols + col];
    }

    std::size_t rows() const noexcept
    {
        return m_rows;
    }

    std::size_t columns() const noexcept
    {
        return m_cols;
    }

    // check if two matrices are equal
    bool operator==(const int_matrix_t& rhs) const
    {
        if (m_rows != rhs.m_rows) return false;
        if (m_cols != rhs.m_cols) return false;
        return m_data == rhs.m_data;
    }

private:
    std::size_t m_rows{}; // always initialized to 0
    std::size_t m_cols{}; // always initialized to 0

    // do not use std::vector<std::vector<int>> as it results in data not being contiguous in memory
    // which is not cache friendly and will slow down your calculations
    std::vector<int> m_data{}; 
};

std::ostream& operator<<(std::ostream& os, const int_matrix_t& matrix)
{
    os << "[\n";
    for(std::size_t row{0ul}; row < matrix.rows(); ++row)
    {
        os << "[";
        bool comma{false};
        for(std::size_t col{0ul}; col < matrix.columns(); ++col)
        {
            if (comma) os << ",";
            os << matrix.at(row,col);
            comma = true;
        }
        os << "]\n";
    }
    os << "]\n";
    return os;
}


int main()
{
    int_matrix_t a
    {{
        {-1,-1,4},
        {0,3,-3},
        {2,-1,-2}
    }};

    int_matrix_t b
    {{
        {3,2,3},
        {2,2,1},
        {2,1,1}
    }};

    int_matrix_t expected
    {{
        {3,0,0},
        {0,3,0},
        {0,0,3}
    }};
    

    int_matrix_t c = a * b;

    // this is where operator== is used
    assert(c == expected);

    std::cout << c;
    
    return 0;
}