Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Infinite loop in GenerateShuffleArray on unix64 #26054

Closed
jakobbotsch opened this issue Aug 7, 2019 · 6 comments · Fixed by #26169

Comments

@jakobbotsch
Copy link
Contributor

commented Aug 7, 2019

The following example gets stuck in an infinite loop in GenerateShuffleArray on unix64:

internal class Program
{
    private static int Main()
    {
        FooDelegate f = Foo;
        return 100;
    }

    static int Foo(long a, long b, long c, long d, S16 e, S24 f, long g, long h)
    {
        return 42;
    }

    delegate int FooDelegate(long a, long b, long c, long d, S16 e, S24 f, long g, long h);

    struct S16 { long A, B; }
    struct S24 { long A, B, C; }
}
@jashook

This comment has been minimized.

Copy link
Member

commented Aug 7, 2019

/cc @sergiy-k

@janvorli

This comment has been minimized.

Copy link
Member

commented Aug 13, 2019

I've looked into it. The problem is that the algorithm that generates the shuffle thunk doesn't consider possibility of loops in the shuffling. I have believed there is no such possibility, but the example above shows that it can happen in some corner cases.

The shuffle thunk needs to translate member method arguments
System.Action'7[[System.__Canon, System.Private.CoreLib],[System.__Canon, System.Private.CoreLib],[System.__Canon, System.Private.CoreLib],[System.__Canon, System.Private.CoreLib],[System.__Canon, System.Private.CoreLib],[WrapperStruct, 16833],[System.Int32, System.Private.CoreLib]].Invoke(System.__Canon, System.__Canon, System.__Canon, System.__Canon, System.__Canon, WrapperStruct, Int32)
to static method arguments
Program.MyMethod(System.Object, System.Object, System.Object, System.Object, System.Object, WrapperStruct, Int32)

So effectively, we are removing "this" from the argument list.
The source argument list is passed in registers / on stack as follows (Sx means stack slot x):

this a b c d e.A e.B f.A f.B f.C g h
RDI RSI RDX RCX R8 S0 S1 S2 S3 S4 R9 S5

The destination arguments are passed like this:

a b c d e.A e.B f.A f.B f.C g h
RDI RSI RDX RCX R8 R9 S0 S1 S2 S3 S4

The cycle is formed by the following shuffle: S1->R9, S3->S1, R9 -> S3. The "e" argument is transferred from S0, S1 to R8, R9, the "g" argument from R9 to S3 and the "f" argument from S2, S3, S4 to S0, S1, S2.

We will need to enhance the algorithm to detect and handle loops.

@jakobbotsch

This comment has been minimized.

Copy link
Contributor Author

commented Aug 13, 2019

Perhaps overkill, but you might consider using Tarjan's algorithm. It will detect strongly connected components (the cycles in this case) and also return them in reverse topological order so things can be done efficiently like before.

@janvorli

This comment has been minimized.

Copy link
Member

commented Aug 13, 2019

@jakobbotsch thank you for the suggestion. I've already used Tarjan algorithm for other purposes in the past. However, for our purposes, I've found a simpler solution that takes advantage of the fact that all vertices in the graph have at most one incoming and one outgoing edge. The complexity is O(V).

@jakobbotsch

This comment has been minimized.

Copy link
Contributor Author

commented Aug 13, 2019

If you need testing for your solution I found this edge case using my ABIStress test (being added in #26090). There is also a standalone version here: https://github.com/jakobbotsch/ABIStress

It should reproduce the problem quickly when run with the arguments --pinvokes --num-calls 1000.

@janvorli

This comment has been minimized.

Copy link
Member

commented Aug 14, 2019

@jakobbotsch thank you! I have tried to use your ABIStress to verify my fix. It passes ok with it. I've ran100000 iterations.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.