free(): invalid pointer, Aborted

[alelvb]

Hello folks,
I've written the following code (that I report entirely)
of which I'm not able to find the bug.

I explain the scenario better for comprehension.

Originally this code was realized using a std::vector of pointers to
T (the code uses templates).
I rewrote the code using a std::vector of std::vector<T> but I get the
same error: it computes the determinant of 1,2 and 3 dimensions matrices
but it fails to do the computing with larger dimensions.
The error given is reported in the subject of this message and is
obviously related to memory deletion.
But to avoid to handle raw pointers I switched to std::vector so I don't
know what else can I do if not ask to more expert programmers.

Thank you

//********** code follows ***********

#include <initializer_list>
#include <iostream>
#include <vector>

using uInt = long long unsigned int;

template <typename T>
class Matrix
{
/* ===================
* the Matrix class
* =================== */
public:

/* ===================
* the constructors
* =================== */

Matrix(std::initializer_list<std::initializer_list<T>> lil);
Matrix(std::initializer_list<T> il, char type = 'r');
Matrix(const Matrix<T>& m) = default;
Matrix(Matrix<T>&& r) = default;
Matrix(uInt r, uInt c);
Matrix() = delete;
~Matrix() = default;

/* ===================
* assignment oper.
* =================== */

Matrix<T>& operator=(const Matrix<T>& m) = default;
Matrix<T>& operator=(Matrix<T>&& m) = default;

/* ===================
* friend functions
* =================== */

friend std::ostream& operator<< (std::ostream& out, const Matrix<T>& m)
// the put in operator
{
for(uInt i=0; i < m.row; i++)
{
for(uInt j=0; j < m.col; j++)
{
out << m.data[i][j] << ' ';
}
out << '\n';
}
return out;
}

friend Matrix<T> operator* (const double s, const Matrix<T>& m)
{
Matrix<T> result(m.row, m.col);

for(uInt i=0; i < m.row; i++)
{
for(uInt j=0; j < m.col; j++)
{
if(m[i][j] != 0)
result[i][j] = s * m[i][j];
}
}
return result;
}

friend T determinant(Matrix<T> &matrix, uInt dim)
{
T Det = 0;

Matrix<T> mC(matrix.row, matrix.col);

if(matrix.row != matrix.col)
{
std::cout << "The determinant of a matrix is defined "
<< "for square matrices only." << '\n';
exit(0);
}
if(dim == 1)
{
return matrix[0][0];
}
else
{
for(uInt i=0; i < matrix.col; i++)
{
if(matrix[0][i] != 0)
{
mC = matrix.submatrix(i);
Det += mC.sign(0,i) * matrix[0][i] * determinant(mC, dim-1);
}
}
}
return Det;
}

/* ===================
* member functions
* =================== */

uInt rows()
{
return row;
}
uInt columns()
{
return col;
}

T trace();
Matrix<T> traspose();
Matrix<T> submatrix(uInt c) const;

std::vector<T> operator[] (const uInt r) const
{
return data[r];
}
std::vector<T>& operator[] (const uInt r)
{
return data[r];
}

Matrix<T> operator+(const Matrix<T>& m);
Matrix<T> operator-(const Matrix<T>& m);
Matrix<T> operator- ();

Matrix<T> operator*(T s);
Matrix<T> operator*(const Matrix<T>& m);

/* ===================
* data members
* =================== */

private:
std::vector<std::vector<T>> data;
uInt row;
uInt col;

int sign(uInt r, uInt c)
{
return ((r+c)%2 == 0) ? 1 : -1;
}
};

/* ===================
* constructor implem
* =================== */

template <typename T>
Matrix<T>::Matrix(std::initializer_list<std::initializer_list<T>> lil)
{
uInt r=0, count=0, maxcols=0;

for(auto y : lil)
{
r++;
std::vector<T> v;
data.push_back(v);

for(auto x : y)
{
count++;
}

if(count > maxcols)
{
maxcols = count;
}
count=0;
}

row = r;
col = maxcols;

// initialization
int i=0;
for(auto y : lil)
{
for(auto x : y)
{
data[i].push_back(x);
}
i++;
}
}

template <typename T>
Matrix<T>::Matrix(std::initializer_list<T> li, char type)
{
uInt i=0;
std::vector<T> d;

switch(type)
{
case 'r':
for(auto x : li)
{
d.push_back(x);
i++;
}
row = 1;
col = i;

data.push_back(d);
break;

case 'c':
i=0;
for(auto x : li)
{
d.erase(d.begin(), d.end());
d.push_back(x);
data.push_back(d);
i++;
}
col = 1;
row = i;
break;

default:
std::cout << "possible values are:"
"\nc for column vector"
"\nr for row vector" << '\n';
exit(0);
break;
}
}

template <typename T>
Matrix<T>::Matrix(uInt r, uInt c)
: row (r),
col (c)
{
for(uInt i=0; i < r; i++)
{
std::vector<T> v;

for(uInt j=0; j < c; j++)
{
v.push_back(static_cast<T>(0));
}

data.push_back(v);
}
}

/* ===================
* member funct impl
* =================== */

template <typename T>
Matrix<T> Matrix<T>::submatrix(uInt c) const
{
uInt dim = row;

if(c >= dim)
{
std::cout << "column index out of range" << '\n';
exit(-1);
}

Matrix<T> m(dim-1, dim-1);

for(uInt i=0; i < m.row; i++)
{
for(uInt j=0; j <= c; j++)
{
m[i][j] = data[i+1][j];
}
for(uInt j=c; j < m.col; j++)
{
m[i][j] = data[i+1][j+1];
}
}
return m;
}

template <typename T>
Matrix<T> Matrix<T>::operator+(const Matrix<T>& m)
{
if((col == m.col) and (row == m.row))
{
Matrix<T> result(row, col);

for(uInt i=0; i < row; i++)
{
for(uInt j=0; j < col; j++)
{
result[i][j] = ( ((*this)[i])[j] + m[i][j]);
}
}
return result;
}
else
{
std::cout << "To sum two matrices they have to have the same "
<< "dimensions" << '\n';
exit(-1);
}
}

template <typename T>
Matrix<T> Matrix<T>::operator- (const Matrix<T>& m)
// binary minus operator
{
return ((*this) + (m * -1));
}

template <typename T>
Matrix<T> Matrix<T>::operator- ()
// unary minus operator
{
return ((*this) * -1);
}

template <typename T>
Matrix<T> Matrix<T>::operator*(const T s)
{
Matrix<T> result(row, col);

for(uInt i=0; i < row; i++)
{
for(uInt j=0; j < col; j++)
{
if((*this)[i][j] != 0)
result[i][j] = s * (*this)[i][j];
}
}
return result;
}

template <typename T>
Matrix<T> Matrix<T>::operator*(const Matrix<T>& m)
{
Matrix<T> result(row, m.col);
T sum = 0;

if(col == m.row)
{
for(uInt i=0; i < row; i++)
{
for(uInt j=0; j < row; j++)
{
for(uInt k=0; k < col; k++)
{
sum += (*this)[i][k] * m[k][j];
}
result[i][j] = sum;
sum = 0;
}
}
return result;
}
else
{
std::cout << "the number of colums of the left matrix operand must\n"
<< "equal the number of rows of the right matrix
operand" << '\n';
exit(-1);
}
}

template <typename T>
T Matrix<T>::trace()
{
if(row != col)
{
std::cout << "Trace operation is defined "
<< "for square matrices only." << '\n';
exit(0);
}

T sum = 0;

for(uInt i=0; i < row; i++)
{
sum += data[i][i];
}
return sum;
}

template <typename T>
Matrix<T> Matrix<T>::traspose()
{
Matrix<T> tr(col, row);

for(uInt i=0; i < row; i++)
{
for(uInt j=0; j < col; j++)
{
tr[j][i] = data[i][j];
}
}
return tr;
}

/* ===================
* the main function
* =================== */

int main()
{
Matrix<double> m {{0,0,0,2},{0,0,1,1},{2,1,0,1},{0,1,1,0}}; //NO
//Matrix<double> m {{0,1,0},{0,1,2},{1,0,1}}; //OK
//Matrix<double> m {{-1,2},{0,1}}; //OK
//Matrix<double> m {2}; //OK

std::cout << m << '\n';
std::cout << "Determinant = " << determinant(m, m.rows());
}

[Paavo Helde]

05.06.2020 15:45 alelvb kirjutas:
> Hello folks,
> I've written the following code (that I report entirely)
> of which I'm not able to find the bug.
>
> I explain the scenario better for comprehension.
>
> Originally this code was realized using a std::vector of pointers to
> T (the code uses templates).
> I rewrote the code using a std::vector of std::vector<T> but I get the
> same error: it computes the determinant of 1,2 and 3 dimensions matrices
> but it fails to do the computing with larger dimensions.
> The error given is reported in the subject of this message and is
> obviously related to memory deletion.
> But to avoid to handle raw pointers I switched to std::vector so I don't
> know what else can I do if not ask to more expert programmers.
>
> Thank you

The debugger shows index out of bounds assert failure in submatrix()
function, with j = 3.

for (uInt j = 0; j <= c; j++) {

m[i][j] = data[i+1][j];
}

I guess you want 'j < c' instead of 'j <= c'.

[alelvb]

Il 05/06/20 18:08, Paavo Helde ha scritto:

Thank you Mr Helde,
that was right the problem. Now it works. If I tell you that I watched
the code for a couple of days without any clue do you believe me?

Thank you so so much.

But the curious thing is that it worked for size smaller than 4.
thank you

[Dash]

No it doesn't work either.

Replace the line

Matrix<double> m {{0,1,0},{0,1,2},{1,0,1}}; //OK

with
Matrix<double> m {{0,0,1},{0,1,2},{1,0,1}}; //OK

and you'll get the same bounding error.

-- Dash

[Paavo Helde]

I guess you don't have the right tools, or you don't know how to use
them. My compiler pinpointed the problem in seconds:

Debug Assertion Failed!

Program: C:\WINDOWS\SYSTEM32\MSVCP140D.dll
File: c:\program files (x86)\microsoft visual
studio\2017\professional\vc\tools\msvc\14.11.25503\include\vector
Line: 1796

Expression: vector subscript out of range

>
> Thank you so so much.
>
> But the curious thing is that it worked for size smaller than 4.
> thank you

That's what is called undefined behavior. The code might appear to work,
crash mysteriously, or fail with assert failures like above. And yes, in
my setup it also fails with assert failures for smaller sizes than 4.

[alelvb]

Il 05/06/20 23:16, Dash ha scritto:

Hello Dash,
I've replaced the line as you suggested but my code still works:
this is the output:

0 0 1
0 1 2
1 0 1

Determinant = -1

thank you

[alelvb]

Il 05/06/20 23:58, Paavo Helde ha scritto:

>>  > The debugger shows index out of bounds assert failure in submatrix()
>>  > function, with j = 3.
>>  >
>>  >          for (uInt j = 0; j <= c; j++) {
>>  >              m[i][j] = data[i+1][j];
>>  >          }
>>  >
>>  > I guess you want 'j < c' instead of 'j <= c'.
>>
>> Thank you Mr Helde,
>> that was right the problem. Now it works. If I tell you that I watched
>> the code for a couple of days without any clue do you believe me?
>
> I guess you don't have the right tools, or you don't know how to use
> them. My compiler pinpointed the problem in seconds:

Maybe the second ;)

> Debug Assertion Failed!
>
> Program: C:\WINDOWS\SYSTEM32\MSVCP140D.dll
> File: c:\program files (x86)\microsoft visual
> studio\2017\professional\vc\tools\msvc\14.11.25503\include\vector
> Line: 1796
>
> Expression: vector subscript out of range

I use code::blocks 17.01 on Debian 10:

g++ --version
g++ (Debian 8.3.0-6) 8.3.0

My compiler compiled the code without any problem.
I made a newbie error. I'm still learning.
When I tried to debug the code I got a generic message like:

Program received signal SIGABRT, Aborted.

No clues of what was happening or why.

cppcheck does not spot the problem.

When I started playing with programming I tried Java 1.2 and javac
spot array out of bound errors on compilation stage.
I know C++ doesn't have such a feature but in my opinion
it would be a blessing for many people.

Thank you for your kind patience

alessandro

[Jorgen Grahn]

On Sat, 2020-06-06, alelvb wrote:
> Il 05/06/20 23:58, Paavo Helde ha scritto:
>
>>>  > The debugger shows index out of bounds assert failure in submatrix()
>>>  > function, with j = 3.
>>>  >
>>>  >          for (uInt j = 0; j <= c; j++) {
>>>  >              m[i][j] = data[i+1][j];
>>>  >          }
>>>  >
>>>  > I guess you want 'j < c' instead of 'j <= c'.
>>>
>>> Thank you Mr Helde,
>>> that was right the problem. Now it works. If I tell you that I watched
>>> the code for a couple of days without any clue do you believe me?
>>
>> I guess you don't have the right tools, or you don't know how to use
>> them. My compiler pinpointed the problem in seconds:
>
> Maybe the second ;)
>
>> Debug Assertion Failed!
>>
>> Program: C:\WINDOWS\SYSTEM32\MSVCP140D.dll
>> File: c:\program files (x86)\microsoft visual
>> studio\2017\professional\vc\tools\msvc\14.11.25503\include\vector
>> Line: 1796
>>
>> Expression: vector subscript out of range
>
> I use code::blocks 17.01 on Debian 10:
>
> g++ --version
> g++ (Debian 8.3.0-6) 8.3.0
>
> My compiler compiled the code without any problem.
> I made a newbie error. I'm still learning.

Yes, that is stuff you have to learn to investigate. For dealing with
problems in runtime, and on Linux, there are at least these things:

0 - building against debug versions of the library (that's what Paavo did)
1 - building with -fsanitize=something
2 - running the code under a debugger
3 - running the code under Valgrind
4 - crashing, getting a core dump and running /that/ one in a debugger

Different people prefer different tools; I personally mostly do 3 and 4.

> When I tried to debug the code I got a generic message like:
>
> Program received signal SIGABRT, Aborted.
>
> No clues of what was happening or why.

This is a side issue, but that's a bit odd, IMHO. On Unix you
typically get SIGABRT by calling std::abort(), and that's usually (not
always) called by assert() or due to an uncaught exception. In both
cases something more should be printed on standard error.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Melzzzzz]

Try with eg qtcreator, there you can debug line by line and set
breakpoints.



--
current job title: senior software engineer
skills: c++,c,rust,go,nim,haskell...

press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi -- Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi
bili naoruzani. -- Mladen Gogala

[Juha Nieminen]

alelvb <ale...@inwind.it> wrote:
> Hello folks,
> I've written the following code (that I report entirely)
> of which I'm not able to find the bug.

The first and most important rule of asking such programming questions is
to create a *minimal* example that demonstrates the problem. You do not
"report it entirely". You go through the trouble of reducing it to the
absolutely minimal essential clear version that still exhibits the
problem.

There are two main reasons for that.

Firstly, you should put some effort into it rather than expecting others
to do all the work for you. You were lucky that this time someone just
ran the code through a debugger which caught the problem. If it had been
something more complicated, you would have been expecting people to wade
through miles of code to try to find that bug for you.

Secondly, when you go through the process of reducing the program to
the absolutely minimum that replicates the problem, you are essentially
going through a process of elimination, and zoning in the source of the
problem. Chances are that you'll end up finding the bug yourself.

[Bo Persson]

The key here is "seems to work". :-)

The memory allocator is likely to work in even block sizes. So when you
ask for 3 elements, you might get space for 4. Or 8, or 16.

It is still an error to use any extra space.


Bo Persson

[alelvb]

Il 06/06/20 04:31, alelvb ha scritto:

OK, so let's suppose I didn't make the array out of bounds error...
My code would have to function right it is doing now. So how could I
spot the problem?

Now another question arises:
some times the error that I get is something about a double free deletion.

But my code uses just std library items and default destructor, default
copy constructor and default move constructor and some people report the
same issue.
What do you think about?

thank you,
alessandro

[alelvb]

Il 06/06/20 09:02, Juha Nieminen ha scritto:

I'll make treasure of your advices, thank you.

alessandro

[Öö Tiib]

Did you ask that if we suppose that you did not make the error then
how are we supposed to spot problem we just supposed that you did
not introduce? It is impossible to spot errors that weren't made.

>
> Now another question arises:
> some times the error that I get is something about a double free deletion.

A program that you wrote does something different than you think
that it does. It is normal. After decades of programming and knowing
lot of other programmers I can confirm that it happens with everybody
forever. More skill improves abilities to notice and to fix it sooner.

> But my code uses just std library items and default destructor, default
> copy constructor and default move constructor and some people report the
> same issue.
> What do you think about?

The std library classes are not magical. Nonsense can be expressed
using those and lot of situations with those are defined to be
undefined behavior.

So out-of-bounds with operator [] of vector is defined to be
undefined behavior in C++. Your own responsibility as programmer
is to ensure that there are no out of bounds accesses.

If you want to get exceptions for out-of-bounds accesses use
vector::at; if you want to get guaranteed crashes (like Paavo
demonstrated) use debug version of standard library.

[Jorgen Grahn]

On Sat, 2020-06-06, Öö Tiib wrote:
> On Saturday, 6 June 2020 15:09:29 UTC+3, alelvb wrote:

...

>> Now another question arises:
>> some times the error that I get is something about a double free deletion.
>
> A program that you wrote does something different than you think
> that it does. It is normal. After decades of programming and knowing
> lot of other programmers I can confirm that it happens with everybody
> forever. More skill improves abilities to notice and to fix it sooner.
>
>
>> But my code uses just std library items and default destructor, default
>> copy constructor and default move constructor and some people report the
>> same issue.
>> What do you think about?
>
> The std library classes are not magical. Nonsense can be expressed
> using those and lot of situations with those are defined to be
> undefined behavior.

I have to agree with the OP though: double-free errors are a little
bit surprising. I associate those with ownership through raw
pointers, and getting it wrong.

And I agree with you. What's most important is not having bugs, not
what happens when you trigger one.

[Paavo Helde]

06.06.2020 15:09 alelvb kirjutas:
>
> Now another question arises:
> some times the error that I get is something about a double free deletion.
>
> But my code uses just std library items and default destructor, default
> copy constructor and default move constructor and some people report the
> same issue.
> What do you think about?

If your own code does not contain any malloc/new/free/delete, then it is
indeed surprising to get "double free" errors. I can think only of
improper multithreading synchronization or general memory corruption
(i.e. a buffer overwrite similar to the last bug).

One thing is pretty certain, the bug is in your code, not in the
compiler or STL, with 99.99% probability.

[Alf P. Steinbach]

Re compilers it used to be so in the 1980's, when I learned programming.

It's no longer the case that compilers are dependable.

When I code I regularly encounter compiler bugs & extreme limitations.

One MSVC ICE (Internal Compiler Error, a crash) today. Combined with all
the ungood stuff in modern Windows, the Microsoft idea of sabotaging
"technologies" that they (some MS managers) want to discontinue, I have
for some years felt a strong aversion to coding.

The last time I was /surprised/ by the sabotage thing was in the early
2000's. I'd made a nice analog clock as a Windows HTML application via
HTML+TIME. Suddenly one day the latter"technology" had been
discontinued, they'd pulled the rug from under my little app.

I don't know if Windows HTML applications still work. It's an HTML file
with extension .HTA, running in local security context. It seems that
all the desktop gadget "technologies" have disappeared, and they're
similar: HTML, Javascript, local security context or sandbox.

But, back to C++. Did you know, that MSVC has a 16KB limit on string
literals? For example. It's something from original Zortech C I think.


- Alf

[Paavo Helde]

06.06.2020 21:19 Alf P. Steinbach kirjutas:
> On 06.06.2020 19:33, Paavo Helde wrote:
>> 06.06.2020 15:09 alelvb kirjutas:
>>>
>>> Now another question arises:
>>> some times the error that I get is something about a double free
>>> deletion.
>>>
>>> But my code uses just std library items and default destructor, default
>>> copy constructor and default move constructor and some people report the
>>> same issue.
>>> What do you think about?
>>
>> If your own code does not contain any malloc/new/free/delete, then it
>> is indeed surprising to get "double free" errors. I can think only of
>> improper multithreading synchronization or general memory corruption
>> (i.e. a buffer overwrite similar to the last bug).
>>
>> One thing is pretty certain, the bug is in your code, not in the
>> compiler or STL, with 99.99% probability.
>
> Re compilers it used to be so in the 1980's, when I learned programming.
>
> It's no longer the case that compilers are dependable.
>
> When I code I regularly encounter compiler bugs & extreme limitations.

Although I normally stick to much more traditional coding style than
seen in your examples, I have also encountered several compiler bugs -
hence the 99.99% estimation of the bug being in my code, not 100%.

>
> One MSVC ICE (Internal Compiler Error, a crash) today. Combined with all
> the ungood stuff in modern Windows, the Microsoft idea of sabotaging
> "technologies" that they (some MS managers) want to discontinue, I have
> for some years felt a strong aversion to coding.

I believe the key point is to avoid proprietary languages and frameworks
which can disappear on a whim. Hence - C++. If MSVC is discontinued, one
can switch over to another implementation.

>
> The last time I was /surprised/ by the sabotage thing was in the early
> 2000's. I'd made a nice analog clock as a Windows HTML application via
> HTML+TIME. Suddenly one day the latter"technology" had been
> discontinued, they'd pulled the rug from under my little app.
>
> I don't know if Windows HTML applications still work. It's an HTML file
> with extension .HTA, running in local security context. It seems that
> all the desktop gadget "technologies" have disappeared, and they're
> similar: HTML, Javascript, local security context or sandbox.

The MS WebBrowser control (usable in a C++ app) is still working and
apparently can be configured to support any of the broken IE versions
from the past (if we are talking about backward compatibility).

> But, back to C++. Did you know, that MSVC has a 16KB limit on string
> literals? For example. It's something from original Zortech C I think.

No, I did not know that (so obviously the limit has been large enough
for my needs). And it seems to be 64K, not 16K, in my quick test:

1>fatal error C1091: compiler limit: string exceeds 65535 bytes in length

[Ike Naar]

A few style issues about the code you posted:

> friend T determinant(Matrix<T> &matrix, uInt dim)

It looks like the determinant function is not supposed to change the matrix.
If that's indeed the case, make matrix a const reference instead of a
nonconst reference.

It also looks like dim is required to be equal to matrix.rows()-1 (and
to matrix.columns()-1).
If that's indeed the case, remove the dims parameter and use matrix.rows()
(or matrix.columns() instead inside the function.

> int sign(uInt r, uInt c)
> {
> return ((r+c)%2 == 0) ? 1 : -1;
> }

Why is sign() a member function? It doesn't do anything with any member
so it might just as well be a free function.

> template <typename T>
> Matrix<T>::Matrix(std::initializer_list<std::initializer_list<T>> lil)
> {
> uInt r=0, count=0, maxcols=0;
>
> for(auto y : lil)
> {
> r++;
> std::vector<T> v;
> data.push_back(v);
>
> for(auto x : y)
> {
> count++;
> }
>
> if(count > maxcols)
> {
> maxcols = count;
> }
> count=0;
> }

count can be moved inside the loop:

uInt r=0, maxcols=0;

for(auto y : lil)
{
Uint count = 0;
r++;
data.push_back(std::vector<T>());

[alelvb]

Il 06/06/20 17:40, Öö Tiib ha scritto:

My sentence was written after Dash replied to my message in which
I wrote the code with the correction spot by Mr. Helde was finally
working. Dash wrote that the code still get a bad message and I thought
He did the modification But still getting the error message. Since on my
computer the code (not corrected) still worked for dimensions less than
or equal to 3 I wrote what I wrote. That's all.

>> Now another question arises:
>> some times the error that I get is something about a double free deletion.
>
> A program that you wrote does something different than you think
> that it does. It is normal. After decades of programming and knowing
> lot of other programmers I can confirm that it happens with everybody
> forever. More skill improves abilities to notice and to fix it sooner.

> So out-of-bounds with operator [] of vector is defined to be
> undefined behavior in C++. Your own responsibility as programmer
> is to ensure that there are no out of bounds accesses.
>
> If you want to get exceptions for out-of-bounds accesses use
> vector::at; if you want to get guaranteed crashes (like Paavo
> demonstrated) use debug version of standard library.
>

made the substitution after you told me this possibility.
Thank you.