23 Mar, 2009, Kline wrote in the 1st comment:
Votes: 0
So someplace I'm invalidating a node in a list. I can reproduce what causes this, successfully segfault and get a good dump from it. Valgrind also verifies that it's happening within the STL functions themselves, after a call through an update loop I run.

Is there any good way to log, trace, or even get more info about this? Once the data passes to the STL functions I can't seem to print any information within that frame to look at further, so I've come to a stopping point.
23 Mar, 2009, David Haley wrote in the 2nd comment:
Votes: 0
Well, if you can reproduce it, can you get a minimal example that reproduces it so we can see the code? In general you're not supposed to modify containers while iterating over them; only a few containers allow this and sometimes then even under fairly specific circumstances.
23 Mar, 2009, elanthis wrote in the 3rd comment:
Votes: 0
Is this a list as in std::list<> ?

The only way to invalidate a (technically, an iterator) there is to delete it with the erase list method. Look for calls to erase. In general when you iterate over any kind of STL container and then call functions that might result in an element being removed you need to jump through some hoops. One way is to make a copy of the container and iterate over that. There are more efficient but quite a bit more complicated methods.

e.g., instead of

for (list<foo>::iterator i = mylist.begin(), e = mylist.end(); i != e; ++i) { update_code; }


You want:

list<foo> tmp = mylist;
for (list<foo>::iterator i = tmp.begin(), e = tmp.end(); i != e; ++i) { update_code; }


The more complicated methods involve keeping around a copy of the "current" update iterator that your node removal routines (mob_kill, whatever) can check and increment if the iterator points to the element being removed.

No different than using a linked list in C and removing the element that an update loop is currently pointing to.

I don't have any particularly good debugging suggestions other than to set a breakpoint on any code that calls erase and step through until you find the culprit.
23 Mar, 2009, Kline wrote in the 4th comment:
Votes: 0
Yes, this is a std::list. I do (potentially) erase elements while iterating it, but thought that was safe to do as long as you point the iterator to erase, ie.
iter = list.erase(iter)
since erase returns the next value.

Either way these are only "shouldn't be here" cases, and I haven't seen them log yet.
void combat_update( void )
{
… declares

for( li = fight_list.begin(); li != fight_list.end(); li++ )
{
ch = *li;
if( ch == NULL )
{
monitor_chan("Removing a null ch from queue.",MONITOR_DEBUG);
li = fight_list.erase(li);
}
if( ch->fighting == NULL )
{
monitor_chan("Removing a null ch->fighting from queue.",MONITOR_DEBUG);
li = fight_list.erase(li);
}
victim = ch->fighting;
… do_more_stuff()
}
}


The only other reference to erase is in stop_fighting(), which is the caller prior to my crash since you mention looking for erase, so here's that chunk of code too:
void stop_fighting( CHAR_DATA * ch, bool fBoth )
{
std::list<CHAR_DATA *>::iterator li;
CHAR_DATA *victim = ch->fighting;

ch->position = POS_STANDING;
update_pos( ch );
fight_list.remove(ch);

if( !fBoth )
{
ch->fighting = NULL;
return;
}

for( li = fight_list.begin(); li != fight_list.end(); li++ )
{
if( *li == victim )
{
victim->position = POS_STANDING;
update_pos( victim );
victim->fighting = NULL;
li = fight_list.erase(li);
}
}
ch->fighting = NULL;
return;
}
24 Mar, 2009, kiasyn wrote in the 5th comment:
Votes: 0
how i did it:

for (list<foo>::iterator i = mylist.begin(); i != mylist.end(); ) {
if ( /* delete condition */ ) {
mylist.erase(i++);
} else

++i;
}
}
24 Mar, 2009, Kline wrote in the 6th comment:
Votes: 0
Still dying in the same spot for me with that. This time it was a bit more clear, though, in that it specifically didn't like the assignment made on line 7 of my first code block.
24 Mar, 2009, elanthis wrote in the 7th comment:
Votes: 0
Kline said:
Yes, this is a std::list. I do (potentially) erase elements while iterating it, but thought that was safe to do as long as you point the iterator to erase, ie.
iter = list.erase(iter)
since erase returns the next value.


Only if that's the actual iterator being used in the actual loop. If you delete items from a list in other functions, that means making the update iterator a global (or accessible through some other means), and not just a copy of the iterator.

The code you posted is also wrong in another way, which could definitely be your crasher. You are incrementing the iterator on every loop, even if the iterator was deleted.

For example, say your list has three items: A, B, and C.

The loop iterator IT is pointing at B. You then delete B, so IT = erase(IT) means that IT now points at C. The end of the loop is reached and the code does a ++IT, pointing it at the end marker. Loop exits without ever looking at C.

Do the same loop, but this time delete C while on it. IT = erase(IT) results in IT pointing to the end marker. Then ++IT is executed by the for loop… and you get a crash.

When you delete items from a list you must only increment the iterator when it's not being deleted. e.g.:

iter = list.begin();
while (iter != list.end()) {
if (need_to_delete)
iter = list.erase(iter);
else
++iter;
}


(ninja'd by kiasyn, who also knows the way of C++ well)
24 Mar, 2009, Kline wrote in the 8th comment:
Votes: 0
Thanks all, and for the explanation elthanis; didn't quite look at it that way. After kiasyn's post I was using
if( delete )
list.erase(iter++)
if( delete )
list.erase(iter++)

do_stuff()
++iter


I am now using the following, and haven't managed to reproduce my problem yet – lets hope it sticks :)
if( delete )
list.erase(iter++)
else if( delete )
list.erase(iter++)
else
++iter

do_stuff()


edit: So no segfault (yet?) yet Valgrind is quite unhappy, lol…Back to poking at this a little more.
24 Mar, 2009, David Haley wrote in the 9th comment:
Votes: 0
I'd go with the code elanthis posted: set iter to the return result of the erase call. Also, look at this:
if( delete )
list.erase(iter++)
else if( delete )
list.erase(iter++)

You're testing the same condition twice, and doing the same thing in either case. Probably only need one of these.
24 Mar, 2009, Kline wrote in the 10th comment:
Votes: 0
David: Well, I have two separate delete conditions, I probably should have been more clear in my example but I did condense them to one, at any rate :).
24 Mar, 2009, elanthis wrote in the 11th comment:
Votes: 0
Looking at the code he posted, his actual code doesn't have the same repetition as the pseudo code. :)

So far as Valgrind.. make it happy. :) It very rarely give false positives.
24 Mar, 2009, ghasatta wrote in the 12th comment:
Votes: 0
Kline said:
I am now using the following, and haven't managed to reproduce my problem yet – lets hope it sticks :)
if( delete )
list.erase(iter++)
else if( delete )
list.erase(iter++)
else
++iter

do_stuff()


edit: So no segfault (yet?) yet Valgrind is quite unhappy, lol…Back to poking at this a little more.


I think Valgrind is unhappy because you are doing post-increment operations on invalid iterators. The post-increment operator doesn't do its thing until after the erase() call completes. And at that point, the iterator is no longer valid. Also, are you using a 'for' loop still? I think the point that Elanthis made about incrementing the end iterator is probably still a concern that you have to address, based on the limited fragment you posted.
24 Mar, 2009, elanthis wrote in the 13th comment:
Votes: 0
Doh, good catch ghasatta.

The iteration is correct in the else clause. You should NOT be doing any increment on the erase call. The returned iterator from erase points to the next element in the list. That is, erase is already incrementing the iterator. You don't need to increment it yourself. You want the _return value_ of erase. For many containers, adding or removing elements invalidates _all_ iterators, not just the one being erased, and the STL container API was designed around that fact.

Quote
if (delete)
iter = list.erase(iter);
else
++iter;
24 Mar, 2009, David Haley wrote in the 14th comment:
Votes: 0
DavidHaley said:
I'd go with the code elanthis posted: set iter to the return result of the erase call.

:sad:
I should have bolded that part and not made the other comment :tongue:
24 Mar, 2009, elanthis wrote in the 15th comment:
Votes: 0
You totally dropped the ball on that one, man.

(Just ribbin' ya. :)
25 Mar, 2009, Kline wrote in the 16th comment:
Votes: 0
Updated to elanthis' while() suggestion and that seems to have made Valgrind very happy indeed :). Thanks! Now to track down a few other (unrelated) obscure bugs (of the non-crashing type)…
09 Apr, 2009, MaineCoon wrote in the 17th comment:
Votes: 0
There are other potential risks involved, such as erasing the iterator from the list within some function further down the callstack than the point of iteration. For example, iterating over a list of characters in a room, dealing damage to them, which may in turn remove one of them. That's a simple case; in my MUD a lot of our gameplay logic is scripted, so the cases get far more complex (cascade events resulting in unpredictable removals from lists).

My solution is to use my own STL interface compliant list class. List nodes are reference counted and have an 'erased' bit. Iterators increment the ref count when they step onto a node, and decrement when stepping off (by calling functions on the nodes). Iterators will skip nodes flagged as erased. If a node's refcount is decremented to 0, it unlinks and deletes itself.

I haven't had a single list-related bug in many years, and I don't have to worry much about when I remove items from the lists. The overhead is miniscule. This in combination with my game entities' physical deletions being deferred to a safe point in the main loop (with purged flags), has saved me many headaches.
0.0/17