View Issue Details
ID | Project | Category | View Status | Date Submitted | Last Update |
---|---|---|---|---|---|
0002165 | FSSCP | graphics | public | 2010-03-27 11:56 | 2012-12-17 09:05 |
Reporter | avaman | Assigned To | Goober5000 | ||
Priority | normal | Severity | crash | Reproducibility | random |
Status | resolved | Resolution | fixed | ||
Product Version | 3.6.12 RC1 | ||||
Summary | 0002165: Vector iterator becomes invalid in Particle.cpp | ||||
Description | In function particle_move_all() the vector iterator "p" inside a loop becomes invalid after manipulation of the vector itself. Tested with "The babylon project". My fixed version attached. | ||||
Tags | No tags attached. | ||||
2010-03-27 11:56
|
particle_move_all.txt (1,271 bytes)
void particle_move_all(float frametime) { MONITOR_INC( NumParticles, Num_particles ); if ( !Particles_enabled ) return; if ( Particles.empty() ) return; //MOD for (SCP_vector<particle>::iterator p = Particles.begin(); p != Particles.end(); ) { for ( uint i = 0; i < Particles.size(); ) { // ADDED particle * p = &Particles[i]; if (p->age == 0.0f) { p->age = 0.00001f; } else { p->age += frametime; } // if it's time expired, remove it if (p->age > p->max_life) { // special case, if max_life is 0 then we want it to render at least once if ( (p->age > frametime) || (p->max_life > 0.0f) ) { *p = Particles.back(); Particles.pop_back(); continue; } } // if the particle is attached to an object which has become invalid, kill it if (p->attached_objnum >= 0) { // if the signature has changed, or it's bogus, kill it if ( (p->attached_objnum >= MAX_OBJECTS) || (p->attached_sig != Objects[p->attached_objnum].signature) ) { *p = Particles.back(); Particles.pop_back(); continue; } } // move as a regular particle else { vm_vec_scale_add2( &p->pos, &p->velocity, frametime ); } // next particle //MOD ++p; i ++; } } |
|
It's easier if you provide .patch files a generated by your svn application rather than text files like that. |
|
I've used SVN very rarely. Thanks for the info. Now I know what these patches mean. |
2010-03-29 12:05
|
fix_2165.diff (624 bytes)
Index: code/particle/particle.cpp =================================================================== --- code/particle/particle.cpp (revision 6028) +++ code/particle/particle.cpp (working copy) @@ -262,7 +262,10 @@ if ( Particles.empty() ) return; - for (SCP_vector<particle>::iterator p = Particles.begin(); p != Particles.end(); ) { + for ( uint i = 0; i < Particles.size(); ) + { + particle * p = &Particles[i]; + if (p->age == 0.0f) { p->age = 0.00001f; } else { @@ -296,10 +299,9 @@ } // next particle - ++p; + ++i; } } - // kill all active particles void particle_kill_all() { |
|
I've attached a patch file which represents the same fix, called "fix_2165.diff". |
|
I put a fix in for that back when I overhauled the particle code to use a free-queue (that was optimisation round 1), but it appears to have been reverted. Additionally, I remember seeing in some GameDev presentations that using .size could represent a small performance hit, especially in loops - better to stick with iterators and reload them when they're invalidated. |
|
I think I've seen this issue in Diaspora -- looking into the patch |
|
This patch throws compilation errors with Clang on latest trunk r8642. It will have to be rewritten, as it doesn't look like it is based off an unmodified trunk codebase? |
|
Not only that but this whole code is completely wrong. You cant remove arbitrary entries from a std::vector without causing a realloc. What seems to be required here is a change to a linked list. EDIT: Attached a patch that should work |
|
particle.cpp.patch (2,442 bytes)
Index: code/particle/particle.cpp =================================================================== --- code/particle/particle.cpp (revision 9388) +++ code/particle/particle.cpp (working copy) @@ -23,7 +23,7 @@ #endif int Num_particles = 0; -static SCP_vector<particle*> Particles; +static SCP_list<particle*> Particles; int Anim_bitmap_id_fire = -1; int Anim_num_frames_fire = -1; @@ -75,14 +75,10 @@ // only call from game_shutdown()!!! void particle_close() { - while (!Particles.empty()) - { - particle* part = Particles.back(); - part->signature = 0; - delete part; - - Particles.pop_back(); + for (SCP_list<particle*>::iterator p = Particles.begin(); p != Particles.end(); ++p) { + delete *p; } + Particles.clear(); } void particle_page_in() @@ -252,7 +248,7 @@ if ( Particles.empty() ) return; - for (SCP_vector<particle*>::iterator p = Particles.begin(); p != Particles.end(); ) { + for (SCP_list<particle*>::iterator p = Particles.begin(); p != Particles.end(); ++p) { particle* part = *p; if (part->age == 0.0f) { part->age = 0.00001f; @@ -266,10 +262,7 @@ if ( (part->age > frametime) || (part->max_life > 0.0f) ) { part->signature = 0; delete *p; - *p = NULL; - - *p = Particles.back(); - Particles.pop_back(); + p = Particles.erase(p); continue; } } @@ -282,10 +275,7 @@ { part->signature = 0; delete *p; - *p = NULL; - - *p = Particles.back(); - Particles.pop_back(); + p = Particles.erase(p); continue; } } @@ -293,9 +283,6 @@ else { vm_vec_scale_add2( &part->pos, &part->velocity, frametime ); } - - // next particle - ++p; } } @@ -306,13 +293,10 @@ Num_particles = 0; Num_particles_hwm = 0; - while (!Particles.empty()) - { - particle* part = Particles.back(); - part->signature = 0; - delete part; - Particles.pop_back(); + for (SCP_list<particle*>::iterator p = Particles.begin(); p != Particles.end(); ++p) { + delete *p; } + Particles.clear(); } MONITOR( NumParticlesRend ) @@ -363,7 +347,7 @@ if ( Particles.empty() ) return; - for (SCP_vector<particle*>::iterator p = Particles.begin(); p != Particles.end(); ++p) { + for (SCP_list<particle*>::iterator p = Particles.begin(); p != Particles.end(); ++p) { particle* part = *p; // skip back-facing particles (ripped from fullneb code) // Wanderer - add support for attached particles |
|
I've got a question on the use of a linked list - how many elements are we expecting the list to contain? I've seen in other areas of the code (r9128) that large lists (maybe 50k-100k+ entries) perform *extremely* slowly when you need to iterate over every entry in the list. I think it's something to do with data locality & caches. Of course, if the number of expected list entries is small, it really doesn't matter (see premature optimisation ;). |
|
Valathil your linked list patch looks fine. |
|
Fix committed to trunk@9411. |
|
Putting this to code review because I'd like to see an answer to niffiwan's question as well. >.> Also, I would like to know whether the order of particles in the vector is significant. If the order doesn't matter, then an easy way to delete items from the middle of the vector is to swap the nth element with the last element, then decrease the size by 1. |
|
That exact thing was done before the fix. Normally pop_back shouldn't cause an iterator invalidation and i checked the original code and can't see how this even happened in the first place. List size is dependent on how much particles are active but i think in even the biggest battle situations it wont get over 10k. So we either can make it a vector again and risk the corruption again that should'nt happen in the first place or just leave the linked list that works as it should. |
|
10k entries is probably fine, I think that's about the size of other list I was referring to when it was working OK (i.e. before the changes that caused it to grow larger) |
|
Personally, I would put it back to vector and take a closer look at why the iterator became invalid. You never know, an additional pair of eyes may be able to help spot the problem. |
|
whatever do what you want not gonna stop you |
|
Is there a test mission that will reliably duplicate the invalidation? |
|
>Personally, I would put it back to vector and take a closer look at why the iterator became invalid. You never know, an additional pair of eyes may be able to help spot the problem. You do know that any manipulation of a vectors' size will invalidate all iterators for that vector, yes? |
|
According to my research, the only iterators that are invalidated are those positioned after the deleted items. If the deleted items are at the end of the vector, then there shouldn't be a problem. |
|
not pop_back google it |
|
I did: http://stackoverflow.com/questions/62340/does-pop-back-really-invalidate-all-iterators-on-an-stdvector "The call to pop_back() removes the last element in the vector and so the iterator to that element is invalidated. The pop_back() call does not invalidate iterators to items before the last element, only reallocation will do that." Anyway, I have further information from Taylor. Stay tuned for an update. |
|
Okay, the issue is that pop_back will invalidate the iterator pointing to the very last particle in the vector. This means that when that particle is removed, the iterator points to nothing rather than pointing to Particles.end() as would be expected. Fixed in r9446. I've also restored the use of SCP_vector because this is far more efficient than SCP_list. |
fs2open: trunk r9411 2012-12-08 22:31 Ported: N/A Details Diff |
Fix for Mantis 2165: Vector iterator becomes invalid in Particle.cpp |
Affected Issues 0002165 |
|
mod - /trunk/fs2_open/code/particle/particle.cpp | Diff File | ||
fs2open: trunk r9445 2012-12-17 03:59 Ported: N/A Details Diff |
revert revision 9411 in preparation for fixing particles (Mantis 0002165) |
Affected Issues 0002165 |
|
mod - /trunk/fs2_open/code/particle/particle.cpp | Diff File | ||
fs2open: trunk r9446 2012-12-17 04:36 Ported: N/A Details Diff |
properly fix the removal of particles (Mantis 0002165) |
Affected Issues 0002165 |
|
mod - /trunk/fs2_open/code/particle/particle.cpp | Diff File |
Date Modified | Username | Field | Change |
---|---|---|---|
2010-03-27 11:56 | avaman | New Issue | |
2010-03-27 11:56 | avaman | File Added: particle_move_all.txt | |
2010-03-27 18:08 | The_E | Note Added: 0011837 | |
2010-03-28 15:52 | avaman | Note Added: 0011840 | |
2010-03-29 12:05 | Genghis | File Added: fix_2165.diff | |
2010-03-29 12:06 | Genghis | Note Added: 0011842 | |
2010-03-29 12:06 | Genghis | Note Edited: 0011842 | |
2010-03-29 12:13 | Genghis | Status | new => assigned |
2010-03-29 12:13 | Genghis | Assigned To | => Genghis |
2010-03-31 11:09 | portej05 | Note Added: 0011846 | |
2012-03-06 13:06 | Echelon9 | Status | assigned => code review |
2012-03-18 14:12 | Echelon9 | Note Added: 0013418 | |
2012-04-01 13:22 | Echelon9 | Note Added: 0013432 | |
2012-04-01 13:22 | Echelon9 | Note Edited: 0013432 | |
2012-12-03 17:29 | Valathil | Note Added: 0014275 | |
2012-12-03 18:08 | Valathil | File Added: particle.cpp.patch | |
2012-12-03 18:08 | Valathil | Note Edited: 0014275 | |
2012-12-09 00:29 | niffiwan | Note Added: 0014364 | |
2012-12-09 01:07 | Echelon9 | Note Added: 0014366 | |
2012-12-09 03:00 | Zacam | Changeset attached | => fs2open trunk r9411 |
2012-12-09 03:00 | Zacam | Note Added: 0014370 | |
2012-12-09 03:00 | Zacam | Status | code review => resolved |
2012-12-09 03:00 | Zacam | Resolution | open => fixed |
2012-12-10 03:47 | Goober5000 | Note Added: 0014400 | |
2012-12-10 03:47 | Goober5000 | Assigned To | Genghis => Valathil |
2012-12-10 03:47 | Goober5000 | Status | resolved => code review |
2012-12-10 03:47 | Goober5000 | Resolution | fixed => reopened |
2012-12-10 19:27 | Valathil | Note Added: 0014411 | |
2012-12-10 21:08 | niffiwan | Note Added: 0014414 | |
2012-12-11 01:14 | Goober5000 | Note Added: 0014417 | |
2012-12-11 01:47 | Valathil | Note Added: 0014418 | |
2012-12-11 02:07 | Goober5000 | Note Added: 0014419 | |
2012-12-11 06:48 | The_E | Note Added: 0014422 | |
2012-12-11 06:51 | Goober5000 | Note Added: 0014423 | |
2012-12-11 07:53 | Valathil | Note Added: 0014424 | |
2012-12-11 16:34 | Goober5000 | Note Added: 0014425 | |
2012-12-11 16:34 | Goober5000 | Assigned To | Valathil => Goober5000 |
2012-12-11 16:34 | Goober5000 | Status | code review => assigned |
2012-12-17 08:28 | Goober5000 | Changeset attached | => fs2open trunk r9445 |
2012-12-17 09:04 | Goober5000 | Changeset attached | => fs2open trunk r9446 |
2012-12-17 09:05 | Goober5000 | Note Added: 0014502 | |
2012-12-17 09:05 | Goober5000 | Status | assigned => resolved |
2012-12-17 09:05 | Goober5000 | Resolution | reopened => fixed |