Valgrind says that const-iterator tries to access uninitialised space, but actually it is

Question

I'm trying to use const_iterators to go through a list of elements (the elements of a matrix).

SparseMatrix matd(5,5,0); //5x5 matrix with 0 as default element.
//Follows elements insertion...
SparseMatrix<int>::const_iterator a,b;
a=matd.cbegin();
b=matd.cend();
while(a!=b){
    cout<<*(a->data)<<endl;
    ++a;
}

But there's something wrong, as valgrind reports.

==4662== Use of uninitialised value of size 8

==4662== at 0x403A19: SparseMatrix::findRow(int) const (SparseMatrix.h:120)

==4662== by 0x40431A: SparseMatrix::findNext(el const*) const (SparseMatrix.h:439)

==4662== by 0x4030B3: SparseMatrix::const_iterator::operator++() (SparseMatrix.h:593)

==4662== by 0x401D63: main (main.cpp:121)

==4662==

==4662== Invalid read of size 4

==4662== at 0x403A27: SparseMatrix::findRow(int) const (SparseMatrix.h:123)

==4662== by 0x40431A: SparseMatrix::findNext(el const*) const (SparseMatrix.h:439)

==4662== by 0x4030B3: SparseMatrix::const_iterator::operator++() (SparseMatrix.h:593)

==4662== by 0x401D63: main (main.cpp:121)

==4662== Address 0xa680020611a25ff is not stack'd, malloc'd or (recently) free'd

==4662==

==4662==

==4662== Process terminating with default action of signal 11 (SIGSEGV)

==4662== General Protection Fault

==4662== at 0x403A27: SparseMatrix::findRow(int) const (SparseMatrix.h:123)

==4662== by 0x40431A: SparseMatrix::findNext(el const*) const (SparseMatrix.h:439)

==4662== by 0x4030B3: SparseMatrix::const_iterator::operator++() (SparseMatrix.h:593)

==4662== by 0x401D63: main (main.cpp:121)

since I use findNext and findRow with normal iterators and other class methods, and they work, I think there's something wrong in operator++():

const_iterator& operator++() { const element *tmp=e; e=sm->findNext(tmp); delete tmp; return *this; }

const_iterator's copy constructor:

const_iterator(const const_iterator& it) { e=it.e; }

Moreover, const_iterators created and used inside a class' method work very well.

PS: The code of findRow

    mrow* findRow(int i) const {
    mrow *tmp = matrix;
    while(tmp!=NULL){
        if(tmp->idx == i) return tmp;
        tmp=tmp->next;
    }   
    return NULL;
}

It passes an if(tmp==NULL) check, so it thinks there's something there in memory, but then it says that it's uninitialized, but I'll say it again, if I use normal iterator it works.

Here's code for findNext

    element* findNext(const element* e) const {
    int r=e->i; 
    int c=e->j;
    int riga,colonna; 
    riga=r;
    while(riga!=-1){
            if(riga==r) {
                mrow *m=findRow(riga); 
                colonna=nextCol(m,c);
                if(colonna!=-1) {
                    T* d=&((findCol(findRow(riga),colonna)->data)); 
                    return genElement(riga,colonna,d);      
                }           
            }
            else{
                colonna=nextCol(findRow(riga),-1);
                if(colonna!=-1) {
                    T* d=&((findCol(findRow(riga),colonna)->data));
                    return genElement(riga,colonna,d);      
                }                       
            }
            riga=nextRow(riga);
    }
    return NULL;
}

Code for constructor SparseMatrix(int,int,T)

    SparseMatrix(int r, int c, T d){
    rows=r;
    cols=c;
    def=d;
    msize=0;
    matrix=NULL;
}

If you need more code just ask.

In addition let me confirm again that I use findRow and findNext for other purposes, and they work. I think that it's something related to constness, but can't get what.

really difficult to answer without atleast some idea of the functions `operator++` and the `find...` functions, just because `tmp` is not null it doesn't mean it's valid - it could be that in your ctor, you don't initialize it with anything... — Nim, Feb 08 '12 at 23:07
@Vektor88 Since the error is in the `SparseMatrix` class, that's the code we'll have to see to be able to help. — Borealid, Feb 08 '12 at 23:13
@Vektor88: Does your SparseMatrix follow the [Rule of 5](http://stackoverflow.com/questions/4782757)? Specifically, your copy constructor, and assignment operator. If not, the error is probably in `findRow` — Mooing Duck, Feb 08 '12 at 23:13
@MooingDuck yes it does and my copy constructor and assignment operator are working properly. But here I'm not even using them. — Vektor88, Feb 08 '12 at 23:18

score 2 · Answer 1 · edited May 23 '17 at 12:06

2

"Use of uninitialised value of size 8 at 0x403A19: SparseMatrix::findRow(int) const (SparseMatrix.h:120)" and "Invalid read of size 4 at 0x403A27: SparseMatrix::findRow(int) const (SparseMatrix.h:123)"

Tells us that you read from a value that was uninitialized, and then three lines later, you dereference an invalid pointer. From the code you shown, those must correspond with these lines:

mrow *tmp = matrix; //matrix is unassigned, but not NULL.  It's random
tmp=tmp->next; //then dereferenced a completely random place in memory

So, this tells me that your object was invalid. If you're certain that the const iterator has something to do with it, I'd imagine the const_iterator's internal SparseMatrix* pointer is incorrect. Can we see the copy constructor and/or the operator++()?

[Edit] Now that I've seen that operator++ deletes it's e member, and assigns it to the result of findNext, we know that e is a pointer that points to dynamically allocated data (an element). We also see that your copy constructor does a shallow copy of that pointer, meaning that as soon as you create one from anther, the temporary is deleted, and the "new" iterator is pointing at invalid memory. And it will "work" sometimes. Except sometimes it won't. Or it could install a virus. Or Whatever. Don't underestimate Undefined Behavior

a=matd.cbegin();
(1) cbegin() creates an iterator, which allocates a new element.
(2) you assign that temporary to a, and copy the pointer.
(3) The temporary is deleted, and deletes the element.
(4) a now points at that (invalid) deleted element

The normal advice at this point, is always assign allocated memory to a smart pointer, almost always a std::unique_ptr, and you won't have this problem ever again. Tip: if you have delete in your code, you're doing it wrong.

edited May 23 '17 at 12:06

Community

1
1

answered Feb 08 '12 at 23:35

Mooing Duck

64,318
19
100
158

But as I'm saying for the third time, if I use normal iterator it doesn't give any error, so it must be the const iterator. Anyway, I'm going to add it too. – Vektor88 Feb 08 '12 at 23:37
@Vektor88: valgrind clearly shows that these are the _direct_ cause of your problem. If we follow this backwards, we'll probably find a chain of events that was somehow triggered by the `const_iterator`, but this is the first step. – Mooing Duck Feb 08 '12 at 23:42
@Vektor88: I realized another possible connection, Can we see const_iterator's copy constructor and/or the operator++()? – Mooing Duck Feb 08 '12 at 23:52
Operator++ is already posted, now I'll add the copy constructor. They're just under the valgrind report. – Vektor88 Feb 08 '12 at 23:57
@Vektor88: no, you posted `operator++(int)`. That doesn't do anything. I'd like to see `operator++()`. They should be two different functions (or maybe we found the problem). Also, what is the type of `const_iterator::e`? It should be `SparseMatrix*`? – Mooing Duck Feb 09 '12 at 00:10
No, both the methods are defined, but I posted the wrong method.I've just posted the right one. e is a private attribute , a pointer to an element struct which contains the coordinates as const int and a pointer to the value stored in the coordinates(i,j). SparseMatrix* is another attribute, also private, named sm. I set it by calling setSM(this) in cbegin() method. – Vektor88 Feb 09 '12 at 00:13
@Vektor88: That's the bug then. `a=matd.cbegin();` (1) `cbegin()` creates an iterator, which allocates a new `element`. (2) you assign that temporary to `a`, and copy the pointer. (3) The temporary is deleted, and deletes it's `element`. (4) `a` now points at that deleted `element`. – Mooing Duck Feb 09 '12 at 00:31
The destructor doesn't delete e, moreover the regular iterator method, begin, does exactly the same and it works. – Vektor88 Feb 09 '12 at 00:42
@Vektor88: If the destructor doesn't delete `e`, why does `operator++()`? There's a contradiction there somewhere. – Mooing Duck Feb 09 '12 at 00:48
Because if I put delete e in destructor, it gives me a double free error, because I attempt to delete it twice, first in the ++, then in the destructor. – Vektor88 Feb 09 '12 at 00:51
1

@Vektor88 Alright, well, either way, that's part of your problem. You either have a double-delete or leaked memory. The fix is the same. You should be able to replace all `element*` with `std::unique_ptr`, and anything that doesn't compile is probably wrong. – Mooing Duck Feb 09 '12 at 00:56
Thanks for your support, I'll try asap to change the whole code with unique ptr – Vektor88 Feb 09 '12 at 01:04

score 1 · Accepted Answer · edited May 23 '17 at 12:14

1

This solved my problem: Use of uninitialised value of size 8

It was an error in the code. In iterator assignment operator I forgot to initialize a fundamental value. This caused all the iterators, with the only exception of begin(), to read in the wrong place as their pointer to sparsematrix wasn't initialized.

edited May 23 '17 at 12:14

Community

1
1

answered Feb 09 '12 at 18:53

Vektor88

4,841
11
59
111

Valgrind says that const-iterator tries to access uninitialised space, but actually it is

2 Answers2