View Issue Details

IDProjectCategoryView StatusLast Update
0002165FSSCPgraphicspublic2012-12-17 09:05
Reporteravaman Assigned ToGoober5000  
PrioritynormalSeveritycrashReproducibilityrandom
Status resolvedResolutionfixed 
Product Version3.6.12 RC1 
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.

Activities

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 ++;
	}
}
particle_move_all.txt (1,271 bytes)   

The_E

2010-03-27 18:08

administrator   ~0011837

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

avaman

2010-03-28 15:52

reporter   ~0011840

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()
 {
fix_2165.diff (624 bytes)   

Genghis

2010-03-29 12:06

developer   ~0011842

Last edited: 2010-03-29 12:06

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

portej05

2010-03-31 11:09

reporter   ~0011846

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.

Echelon9

2012-03-18 14:12

developer   ~0013418

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

Echelon9

2012-04-01 13:22

developer   ~0013432

Last edited: 2012-04-01 13:22

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?

Valathil

2012-12-03 17:29

developer   ~0014275

Last edited: 2012-12-03 18:08

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

Valathil

2012-12-03 18:08

developer  

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
particle.cpp.patch (2,442 bytes)   

niffiwan

2012-12-09 00:29

developer   ~0014364

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

Echelon9

2012-12-09 01:07

developer   ~0014366

Valathil your linked list patch looks fine.

Zacam

2012-12-09 03:00

administrator   ~0014370

Fix committed to trunk@9411.

Goober5000

2012-12-10 03:47

administrator   ~0014400

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.

Valathil

2012-12-10 19:27

developer   ~0014411

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.

niffiwan

2012-12-10 21:08

developer   ~0014414

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)

Goober5000

2012-12-11 01:14

administrator   ~0014417

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.

Valathil

2012-12-11 01:47

developer   ~0014418

whatever do what you want not gonna stop you

Goober5000

2012-12-11 02:07

administrator   ~0014419

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

The_E

2012-12-11 06:48

administrator   ~0014422

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

Goober5000

2012-12-11 06:51

administrator   ~0014423

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.

Valathil

2012-12-11 07:53

developer   ~0014424

not pop_back google it

Goober5000

2012-12-11 16:34

administrator   ~0014425

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.

Goober5000

2012-12-17 09:05

administrator   ~0014502

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.

Related Changesets

fs2open: trunk r9411

2012-12-08 22:31

Zacam


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

Goober5000


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

Goober5000


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

Issue History

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