Bug 19639 - LinkedList throws InvalidOperationException
Summary: LinkedList throws InvalidOperationException
Alias: None
Product: Android
Classification: Xamarin
Component: BCL Class Libraries ()
Version: 4.12.4
Hardware: PC Windows
: Normal normal
Target Milestone: ---
Assignee: Marek Habersack
Depends on:
Reported: 2014-05-09 05:01 UTC by Egorbo
Modified: 2014-07-10 09:51 UTC (History)
3 users (show)

Is this bug a regression?: ---
Last known good build:

Notice (2018-05-24): bugzilla.xamarin.com is now in read-only mode.

Please join us on Visual Studio Developer Community and in the Xamarin and Mono organizations on GitHub to continue tracking issues. Bugzilla will remain available for reference in read-only mode. We will continue to work on open Bugzilla bugs, copy them to the new locations as needed for follow-up, and add the new items under Related Links.

Our sincere thanks to everyone who has contributed on this bug tracker over the years. Thanks also for your understanding as we make these adjustments and improvements for the future.

Please create a new report on Developer Community or GitHub with your current version information, steps to reproduce, and relevant error messages or log files if you are hitting an issue that looks similar to this resolved bug and you do not yet see a matching new report.

Related Links:

Description Egorbo 2014-05-09 05:01:59 UTC
In our game we sometimes receive crash reports with the following stack trace:

System.InvalidOperationException: Operation is not valid due to the current state of the object
at System.Collections.Generic.LinkedList`1<SomeClass>.VerifyReferencedNode (System.Collections.Generic.LinkedListNode`1<SomeClass>) <0x00068> 
at System.Collections.Generic.LinkedList`1<SomeClass>.Remove (System.Collections.Generic.LinkedListNode`1<SomeClass>) <0x0001b> 
at System.Collections.Generic.LinkedList`1<SomeClass>.Clear () <0x0001f> 

Also we used to receive the same exception in LimitedConcurrencyLevelTaskScheduler from http://msdn.microsoft.com/en-us/library/ee789351(v=vs.110).aspx (it uses LinkedList)

I tried to create a repro: http://codepad.org/n0HgKqy8
and it fails from time to time on Samsung Galaxy S5 (rerun sample if it's not crashed)
however, I unable to reproduce it on ios and mono console app - only on Xamarin.Android 4.12.4 and early versions.
Comment 1 Marek Habersack 2014-07-10 09:35:47 UTC

The code you linked to will not work correctly, I'm afraid. It will fail in exactly the way you're seeing because of the way the locking is implemented. The many tasks/threads which execute (up to 4 at the same time on SG5) will randomly add and clear the list. When in the inner loop you acquire the lock, add an item, leave the lock - at this point the .Clear call in another thread may kick in and remove the object you've just added. With enough randomness it will eventually happen that an object will be attempted to remove twice causing this exact exception to be thrown. As such, it is not an issue with Android or Xamarin.Android :(

I would consider using one of the concurrent collections in the System.Collections.Concurrent namespace or changing the locking pattern you use.
Comment 2 Egorbo 2014-07-10 09:40:56 UTC
I agree that provided sample may not be correct, but we use LimitedConcurrencyLevelTaskScheduler from msdn http://msdn.microsoft.com/en-us/library/ee789351(v=vs.110).aspx and it sometimes fail with the error I mentioned :( it has never happened on windows (desktop .net and WP)
Comment 3 Egorbo 2014-07-10 09:45:33 UTC
BTW, Are you trying to say that Clear will throw InvalidOperationException when list is empty?
Comment 4 Marek Habersack 2014-07-10 09:50:34 UTC
(In reply to comment #3)
> BTW, Are you trying to say that Clear will throw InvalidOperationException when
> list is empty?
No, it will happen when the item passed to Remove was already removed somewhere else - it's a race condition.
Comment 5 Marek Habersack 2014-07-10 09:51:51 UTC
You would need to provide a test case that fits better your code (including the scheduler etc.) for me to be able to see what's really going on. For now I can only assume that the code which processes the list is not entirely thread safe.

Note that the MSDN sample you linked to uses a List<> which does NOT verify the node being removed in the way LinkedList does. Even using the scheduler you can run into the issue I described with the sample you provided, especially on slower devices.