2018-10-19 15:24 EDT


View Issue Details Jump to Notes ] Related Changesets ]
IDProjectCategoryView StatusLast Update
0002165FSSCPgraphicspublic2012-12-17 04:05
Reporteravaman 
Assigned ToGoober5000 
PrioritynormalSeveritycrashReproducibilityrandom
StatusresolvedResolutionfixed 
Product Version3.6.12 RC1 
Target VersionFixed in Version 
Summary0002165: Vector iterator becomes invalid in Particle.cpp
DescriptionIn 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.
TagsNo tags attached.
Attached Files
  • txt file icon particle_move_all.txt (1,271 bytes) 2010-03-27 07:56 -
    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 ++;
    	}
    }
    txt file icon particle_move_all.txt (1,271 bytes) 2010-03-27 07:56 +
  • diff file icon fix_2165.diff (624 bytes) 2010-03-29 08:05 -
    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()
     {
    
    diff file icon fix_2165.diff (624 bytes) 2010-03-29 08:05 +
  • patch file icon particle.cpp.patch (2,442 bytes) 2012-12-03 13:08 -
    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
    
    patch file icon particle.cpp.patch (2,442 bytes) 2012-12-03 13:08 +

-Relationships
+Relationships

-Notes

~0011837

The_E (administrator)

It's easier if you provide .patch files a generated by your svn application rather than text files like that.

~0011840

avaman (reporter)

I've used SVN very rarely. Thanks for the info. Now I know what these patches mean.

~0011842

Genghis (developer)

Last edited: 2010-03-29 08:06

I've attached a patch file which represents the same fix, called "fix_2165.diff".

~0011846

portej05 (reporter)

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.

~0013418

Echelon9 (developer)

I think I've seen this issue in Diaspora -- looking into the patch

~0013432

Echelon9 (developer)

Last edited: 2012-04-01 09:22

View 2 revisions

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?

~0014275

Valathil (developer)

Last edited: 2012-12-03 13:08

View 2 revisions

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

~0014364

niffiwan (developer)

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 ;).

~0014366

Echelon9 (developer)

Valathil your linked list patch looks fine.

~0014370

Zacam (administrator)

Fix committed to trunk@9411.

~0014400

Goober5000 (administrator)

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.

~0014411

Valathil (developer)

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.

~0014414

niffiwan (developer)

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)

~0014417

Goober5000 (administrator)

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.

~0014418

Valathil (developer)

whatever do what you want not gonna stop you

~0014419

Goober5000 (administrator)

Is there a test mission that will reliably duplicate the invalidation?

~0014422

The_E (administrator)

>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?

~0014423

Goober5000 (administrator)

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.

~0014424

Valathil (developer)

not pop_back google it

~0014425

Goober5000 (administrator)

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.

~0014502

Goober5000 (administrator)

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.
+Notes

+Related Changesets

-Issue History
Date Modified Username Field Change
2010-03-27 07:56 avaman New Issue
2010-03-27 07:56 avaman File Added: particle_move_all.txt
2010-03-27 14:08 The_E Note Added: 0011837
2010-03-28 11:52 avaman Note Added: 0011840
2010-03-29 08:05 Genghis File Added: fix_2165.diff
2010-03-29 08:06 Genghis Note Added: 0011842
2010-03-29 08:06 Genghis Note Edited: 0011842
2010-03-29 08:13 Genghis Status new => assigned
2010-03-29 08:13 Genghis Assigned To => Genghis
2010-03-31 07:09 portej05 Note Added: 0011846
2012-03-06 08:06 Echelon9 Status assigned => code review
2012-03-18 10:12 Echelon9 Note Added: 0013418
2012-04-01 09:22 Echelon9 Note Added: 0013432
2012-04-01 09:22 Echelon9 Note Edited: 0013432 View Revisions
2012-12-03 12:29 Valathil Note Added: 0014275
2012-12-03 13:08 Valathil File Added: particle.cpp.patch
2012-12-03 13:08 Valathil Note Edited: 0014275 View Revisions
2012-12-08 19:29 niffiwan Note Added: 0014364
2012-12-08 20:07 Echelon9 Note Added: 0014366
2012-12-08 22:00 Zacam Changeset attached => fs2open trunk r9411
2012-12-08 22:00 Zacam Note Added: 0014370
2012-12-08 22:00 Zacam Status code review => resolved
2012-12-08 22:00 Zacam Resolution open => fixed
2012-12-09 22:47 Goober5000 Note Added: 0014400
2012-12-09 22:47 Goober5000 Assigned To Genghis => Valathil
2012-12-09 22:47 Goober5000 Status resolved => code review
2012-12-09 22:47 Goober5000 Resolution fixed => reopened
2012-12-10 14:27 Valathil Note Added: 0014411
2012-12-10 16:08 niffiwan Note Added: 0014414
2012-12-10 20:14 Goober5000 Note Added: 0014417
2012-12-10 20:47 Valathil Note Added: 0014418
2012-12-10 21:07 Goober5000 Note Added: 0014419
2012-12-11 01:48 The_E Note Added: 0014422
2012-12-11 01:51 Goober5000 Note Added: 0014423
2012-12-11 02:53 Valathil Note Added: 0014424
2012-12-11 11:34 Goober5000 Note Added: 0014425
2012-12-11 11:34 Goober5000 Assigned To Valathil => Goober5000
2012-12-11 11:34 Goober5000 Status code review => assigned
2012-12-17 03:28 Goober5000 Changeset attached => fs2open trunk r9445
2012-12-17 04:04 Goober5000 Changeset attached => fs2open trunk r9446
2012-12-17 04:05 Goober5000 Note Added: 0014502
2012-12-17 04:05 Goober5000 Status assigned => resolved
2012-12-17 04:05 Goober5000 Resolution reopened => fixed
+Issue History