[sgen] Fix an infinite loop in find_previous_pointer_fragment due to remove CAS'ing...

The fragment list has one invariant, the next pointer is tagged if the current fragment is been deleted,
which means the list head can never point to a tagged pointer.

If this invariant is broken, the code in find_previous_pointer_fragment will end up in an infinite loop.

The infinite loop happens in this simplified fragment:

try_again:
	prev = &allocator->alloc_head;
1)	cur = unmask (*prev);
	while (1) {
2)		if (*prev != cur)
			goto try_again;

So assume allocator->alloc_head points to 0x121, which is tagged.

So execution goes like this:

1) cur is set to 0x120
2) *prev (value 0x121) is different than cur (value 0x120) so retry.

The above will loop forever as the fixup code never touches allocator->alloc_head.

Now that we understand the infinite loop, let's see how the remove code can trigger it.

Use use the following notation in the event sequence:

-> a non tagged pointer
-*> a tagged pointer
first CAS: InterlockedCompareExchangePointer ((volatile gpointer*)&frag->next, mask (next, 1), next)
second CAS: InterlockedCompareExchangePointer ((volatile gpointer*)prev_ptr, next, frag)

Assuming the following initial fragment list and two threads removing two separate fragments:

fragment list; -> A -> B -> C

thread 1 removes A
thread 2 removes B

thread 2 succeed the first CAS
-> A -> B -*> C

thread 1 succeed the first CAS
-> A -*> B -*> C

thread 2 fail the second CAS because of thread 1
-> A -*> B -*> C

thread 1 succeed the second CAS
-> B -*> C

thread 2 succeed the second CAS and set prev_ptr to next,
which at this point is a tagged pointer. Leaving the fragment list like this:
-*> C

After the last CAS, we end up with alloc_head with a tagged pointer, which will cause
the infinite loop we previously explained.

The fix is to unmask the value we store in the second CAS, as the objective is to link
two live fragments and not flag the previous fragment for deletion.

The exact same bug exists in mono-linked-list-set and was fixed there.

diff --git a/mono/metadata/sgen-nursery-allocator.c b/mono/metadata/sgen-nursery-allocator.c
index 8e3dc1820ee81ff00fd8a1cf2ed138831067d495..4ac1aa0c21160e36f2ae76b9ca3c1d1dfb2645e7 100644 (file)
--- a/mono/metadata/sgen-nursery-allocator.c
+++ b/mono/metadata/sgen-nursery-allocator.c
@@ -414,7 +414,7 @@ par_alloc_from_fragment (SgenFragmentAllocator *allocator, SgenFragment *frag, s
                                /*frag->next read must happen before the first CAS*/
                                mono_memory_write_barrier ();
 
-                               /*Fail if the next done is removed concurrently and its CAS wins */
+                               /*Fail if the next node is removed concurrently and its CAS wins */
                                if (InterlockedCompareExchangePointer ((volatile gpointer*)&frag->next, mask (next, 1), next) != next) {
                                        continue;
                                }
@@ -424,7 +424,7 @@ par_alloc_from_fragment (SgenFragmentAllocator *allocator, SgenFragment *frag, s
                        mono_memory_write_barrier ();
 
                        /* Fail if the previous node was deleted and its CAS wins */
-                       if (InterlockedCompareExchangePointer ((volatile gpointer*)prev_ptr, next, frag) != frag) {
+                       if (InterlockedCompareExchangePointer ((volatile gpointer*)prev_ptr, unmask (next), frag) != frag) {
                                prev_ptr = find_previous_pointer_fragment (allocator, frag);
                                continue;
                        }

diff --git a/mono/utils/mono-linked-list-set.c b/mono/utils/mono-linked-list-set.c
index 3536d25d8445900a99b12dd7b1c67851899b809d..b7391962eaae5d35ab1e704801f7d36e533224aa 100644 (file)
--- a/mono/utils/mono-linked-list-set.c
+++ b/mono/utils/mono-linked-list-set.c
@@ -188,7 +188,7 @@ mono_lls_remove (MonoLinkedListSet *list, MonoThreadHazardPointers *hp, MonoLink
                        continue;
                /* The second CAS must happen before the first. */
                mono_memory_write_barrier ();
-               if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, next, cur) == cur) {
+               if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, mono_lls_pointer_unmask (next), cur) == cur) {
                        /* The CAS must happen before the hazard pointer clear. */
                        mono_memory_write_barrier ();
                        mono_hazard_pointer_clear (hp, 1);