Segmentation fault on list in C++

Question

I'm using a class which holds a private list:

class Set
{
private:
    list<long long unsigned> ways; //holds tags of addresses

and as part of the class's functionality I'm managing a LIFO on the list 'ways':

list<long long unsigned>::iterator it = ways.begin();

while (it!= ways.end()) //looks for the tag in the list
{
    if ((*it) == tag) //tag is found in this set. moves the tag to the end of the list
    {
        ways.erase(it);
        ways.push_back(tag);
        return true;
    }
    it++;
}
return false;

and:

if (occupied < maxWays) //if the set is not all used up just pushes tag in the end
{
    ways.push_back(tag);
    occupied++;
    return false;
}
else // if used up pops the front member (the least recently used one)
{
    ways.pop_front();
    ways.push_back(tag);
}
return true;

Nothing else touches 'ways' and nothing else erases the class 'set'. Multiple instances of the class 'set' are created at the beginning.

During operation I'm getting Segmentation Fault for

list<long long unsigned>::iterator it = ways.begin();

which occurs after a long run. Trying to print the address of 'ways' before this line shows that at the point that I'm about to get Segmentation Fault the address of 'ways' changed dramatically. All the previous times it was around 0x6000xxxxx for each instance, and at that time it was 0x23.

I don't have a clue what can cause that, please assist.

It sounds like either you're destroying the `Set` object, or corrupting its memory somehow. A tool like Valgrind might help track down what's going wrong. Alternatively, try to reduce your program to the smallest possible test case; hopefully, you'll discover the problem while doing that. — Mike Seymour, Aug 25 '14 at 13:34
Just a note, list has `remove()` function which is what you are implementing yourself I think http://www.cplusplus.com/reference/list/list/remove/ — MoonBun, Aug 25 '14 at 13:49
If a data member address is invalid, it means the owner address is invalid. Operations with the data are unlikely to cause this (it's possible but no more likely than with any other erroneous operation). — n. m. could be an AI, Aug 25 '14 at 14:00
@Vladp I checked the address of `ways` after each use, and it stays the same, therefore I don't think that I shall look for a failure in my list operations. — Jaaz, Aug 25 '14 at 14:07
@Mike-Seymour As for destroying the object `Set` I'll try Valgrind. Is there anything that gdb can do to help? — Jaaz, Aug 25 '14 at 14:08
@user3675820 "address of 'ways'" sound extremely suspicious, it should be allocated as a part of the Set object and cannot change unless you reallocate/delete the Set. — MoonBun, Aug 25 '14 at 14:10
@user3675820 Also what about when the list is empty? begin will return an invalid iterator which you can't use. — MoonBun, Aug 25 '14 at 14:13
@Vladp When I'm referring to 'address of ways' I'm referring to the fact that I have many `Set`s therefore each one has its own address. As for an empty list, I don't run into any problem with that; every execution starts with an empty list, and many executions run without any problem (and the ones that fail do that after long run, using these methods many times) — Jaaz, Aug 25 '14 at 14:20
@user3675820: gdb can watch memory, and tell you when it changes. That might also be helpful. — Mike Seymour, Aug 25 '14 at 14:24
If the problem is heap corruption (and it really sounds that way), then the cause could be a subtle error *anywhere* in the code base. Deducing that this part or that part must surely be correct will not get you very far; follow @MikeSeymour's advice. — Beta, Aug 25 '14 at 14:49
@Beta Thank you. I assumed that I'll get to that conclusion (using people's experience here), but yet also were hoping to get debug hints. (which I did) — Jaaz, Aug 25 '14 at 15:15
@MikeSeymour and all, thank you for your assistance! Valgrind did help find the memory leakage which caused my to destroy this structure. — Jaaz, Aug 26 '14 at 14:25

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

2

It might be that you delete an element from the list, and then increment the iterator, which points to the deleted element.

You probably need to forward the iterator first, and then remove the previous, to achieve what you want. See: Can you remove elements from a std::list while iterating through it?

EDIT: See also the return value of erase(), and similar operations that modify the iterator bag. http://www.cplusplus.com/reference/list/list/erase/

edited May 23 '17 at 12:27

Community

1
1

answered Aug 25 '14 at 14:07

Henrik Kjus Alstad

674
2
9
24

he does not use it after erasing an element from the list. – MoonBun Aug 25 '14 at 14:11
I can't boast of knowing the internals of the iterator class, but it could possibly mess up the iterators internals with respect to where it think it is, and how many elements it thinks is left before reaching the end – Henrik Kjus Alstad Aug 25 '14 at 14:14
@HenrikKjusAlstad I checked the address of ways after each use (just before each `return`, and it stays ok, therefore I don't think that I shall look for a failure in my list operations. – Jaaz Aug 25 '14 at 14:22
@user3675820 - `checked the address of ways after each use (just before each return, and it stays ok` That doesn't mean anything. There is no guarantee that a "good looking" address points to a valid object. That can be easily demonstrated like this: `int main() { int *p = new int; delete p; }` The value of `p` doesn't change after the `delete` call, but it still is undefined behavior if I use `p` after the call to `delete`. – PaulMcKenzie Aug 25 '14 at 14:59
@PaulMcKenzie Please see my last paragraph on the original post to understand why this seem important to check and conclude accordingly. – Jaaz Aug 25 '14 at 15:12
@user3675820 My point is that you cannot conclude that things are ok if the address "looks good". The corruption may have even occurred during one of those times you thought the address was ok. Unlike other languages, C++ doesn't automatically crash when you do something wrong. – PaulMcKenzie Aug 25 '14 at 15:46

score 0 · Answer 2 · answered Aug 25 '14 at 17:12

Are you initiliazing 'occupied' and 'maxWays' ? If not, see example where it fails as we are calling ways.pop_front() on empty list ways

class Set
{
public:
    Set(int max) 
    {
        maxWays = max;
        occupied = 10;   // Say randomly stored value 10 is more than maxWays = 5
    }

    bool search(long long tag)
    {
        list<long long unsigned>::iterator it = ways.begin();

        while (it!= ways.end()) {
            if ((*it) == tag) {
                ways.erase(it);
                ways.push_back(tag);

                return true;
            }
            it++;
        }

        return false;
    }

    bool add(long long tag) 
    {
        if (occupied < maxWays) {
            ways.push_back(tag);
            occupied++;
            return false;
        }
        else {
            ways.pop_front();       // may fail here
            ways.push_back(tag);
       }

        return true;
    }

private:
    list<long long unsigned> ways; 
    int maxWays;
    int occupied;
};

int main() 
{
    Set set(5);
    cout << set.add(100) << endl;
    return 0;
}

yes I do. I didn't put it as part of the attached code, but it was obvious from the fact that I stated that it happens after millions of accesses to `Set`. — Jaaz, Aug 26 '14 at 14:28
Without initialized values, it still could happen after million runs. In fact I faced it few years back where uninitialized counter was leading to core where the undefined value was pretty big. — Amit, Aug 27 '14 at 06:19

Segmentation fault on list in C++

2 Answers2