Bug 17897 - MemoryCacheEntryPriorityQueue throws out of bounds on resize
Summary: MemoryCacheEntryPriorityQueue throws out of bounds on resize
Alias: None
Product: Class Libraries
Classification: Mono
Component: System ()
Version: 3.2.x
Hardware: PC Linux
: --- normal
Target Milestone: Untriaged
Assignee: Bugzilla
Depends on:
Reported: 2014-02-19 18:05 UTC by Craig Minihan
Modified: 2014-07-30 11:19 UTC (History)
1 user (show)

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

Simple test case for MonoDevelop 4.0 (3.77 KB, application/x-gzip)
2014-02-19 18:10 UTC, Craig Minihan

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 GitHub or Developer Community 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 Craig Minihan 2014-02-19 18:05:42 UTC
MemoryCacheEntryPriorityQueue used by System.Runtime.Caching.MemoryCache throws an out of bounds exception after a resize).

The problem happens in GetHeapWithShrink(), here:

if ((heapCount < halfTheSize) && newSize > -1)
    Array.Resize <MemoryCacheEntry> (ref heap, newSize);

The array is resized based on the newSize var, however the class has an instance member heapSize which has not been updated. The heap resize calculation masks this issue but can be easily be revealed with this simple test case:

        public static void Main(string[] args)
            var queue = new MemoryCacheEntryPriorityQueue();

            for (int i = 0; i < 10000; i++)
                queue.Enqueue(new MemoryCacheEntry(i));

            for (int i = 0; i < 6000; i++)

            for (int i = 0; i < 10000; i++)
                queue.Enqueue(new MemoryCacheEntry(i)); <== out of bounds happens here

In this example MemoryCacheEntry is a placebo. I found this issue on 3.2.3 - the same code appears on master.

The fix for the out of bounds is to assign heapSize with the value of newSize after the Array.Resize() call.

This code is however subject to a number of other issues, for example HEAP_RESIZE_THRESHOLD is set to 8192, and on a GetHeapWithShrink call where there are more than 8192 entries an Array.Resize() call is make EVERY time a Dequeue occurs - frequently the array size changes by 1 byte.

I'm happy to make the fix for this issue since it is a blocker for me anyway.
Comment 1 Craig Minihan 2014-02-19 18:10:41 UTC
Created attachment 6096 [details]
Simple test case for MonoDevelop 4.0
Comment 2 Craig Minihan 2014-02-19 18:34:18 UTC
A quick mod to the test code shows the resize behavior in more detail:

resize: oldSize=9537, newSize=9537, count=4157
resize: oldSize=9537, newSize=9536, count=4158
resize: oldSize=9536, newSize=9536, count=4159
resize: oldSize=9536, newSize=9536, count=4160
resize: oldSize=9536, newSize=9535, count=4161
resize: oldSize=9535, newSize=9535, count=4162
resize: oldSize=9535, newSize=9535, count=4163
resize: oldSize=9535, newSize=9534, count=4164
resize: oldSize=9534, newSize=9534, count=4165
resize: oldSize=9534, newSize=9534, count=4166
resize: oldSize=9534, newSize=9533, count=4167
resize: oldSize=9533, newSize=9533, count=4168
resize: oldSize=9533, newSize=9533, count=4169
resize: oldSize=9533, newSize=9532, count=4170
resize: oldSize=9532, newSize=9532, count=4171
resize: oldSize=9532, newSize=9532, count=4172
resize: oldSize=9532, newSize=9531, count=4173
resize: oldSize=9531, newSize=9531, count=4174
resize: oldSize=9531, newSize=9531, count=4175
resize: oldSize=9531, newSize=9530, count=4176
resize: oldSize=9530, newSize=9530, count=4177
resize: oldSize=9530, newSize=9530, count=4178
resize: oldSize=9530, newSize=9529, count=4179
resize: oldSize=9529, newSize=9529, count=4180
resize: oldSize=9529, newSize=9529, count=4181
resize: oldSize=9529, newSize=9528, count=4182
resize: oldSize=9528, newSize=9528, count=4183
resize: oldSize=9528, newSize=9528, count=4184
resize: oldSize=9528, newSize=9527, count=4185
resize: oldSize=9527, newSize=9527, count=4186
resize: oldSize=9527, newSize=9527, count=4187
resize: oldSize=9527, newSize=9526, count=4188
resize: oldSize=9526, newSize=9526, count=4189
resize: oldSize=9526, newSize=9526, count=4190
resize: oldSize=9526, newSize=9525, count=4191
>>>> out of bounds here

Apart from the exception case the very large number of resizes seems like another bug which should be addressed.
Comment 3 Craig Minihan 2014-02-19 18:57:13 UTC
Ignore comment 2 above. The assignment of heapSize after the Resize() fixes the over zealous resizing as well.
Comment 4 Craig Minihan 2014-02-28 13:29:53 UTC
Fix make in pull request #928 on GitHub.
Comment 5 Craig Minihan 2014-03-06 07:45:32 UTC
Update: fixed in pull #934.
Comment 6 Craig Minihan 2014-03-25 20:11:16 UTC
Merged into master in: 00853025ec544b18e75cbe1165d1c1478e68fb6e