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 #13225

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

Infinite loop in GenerateShuffleArray on unix64 #13225

jakobbotsch opened this issue Aug 7, 2019 · 6 comments · Fixed by dotnet/coreclr#26169
Assignees

Comments

@jakobbotsch
Copy link
Member

@jakobbotsch jakobbotsch 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
Copy link
Contributor

@jashook jashook commented Aug 7, 2019

/cc @sergiy-k

@janvorli
Copy link
Member

@janvorli janvorli 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
Copy link
Member Author

@jakobbotsch jakobbotsch 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
Copy link
Member

@janvorli janvorli 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
Copy link
Member Author

@jakobbotsch jakobbotsch commented Aug 13, 2019

If you need testing for your solution I found this edge case using my ABIStress test (being added in dotnet/coreclr#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
Copy link
Member

@janvorli janvorli 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.

@msftgits msftgits transferred this issue from dotnet/coreclr Jan 31, 2020
@msftbot msftbot bot locked as resolved and limited conversation to collaborators Dec 12, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

3 participants