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

Runtime Error when using span on LeetCode #13597

Closed
imba-tjd opened this issue Mar 22, 2019 · 1 comment

Comments

@imba-tjd
Copy link

@imba-tjd imba-tjd commented Mar 22, 2019

Steps to Reproduce

  1. Open https://leetcode.com/problems/longest-palindromic-substring/.
  2. Copy and Paste my following code.
  3. Click Run Code

I don't think my code has an algorithm issue because changing span to string works.

public class Solution {
    public string LongestPalindrome(string s) // DP
    {
        ReadOnlySpan<char> ss = s.AsSpan();
        ReadOnlySpan<char> str = "";
        for (int i = 0; i < s.Length; i++)
        {
            var r = Expand(ss, i - 1, i + 1);
            if (r.Length > str.Length)
                str = r;
            r = Expand(ss, i, i + 1);
            if (r.Length > str.Length)
                str = r;
        }
        return str.ToString();
    }
    internal ReadOnlySpan<char> Expand(ReadOnlySpan<char> s, int from, int to)
    {
        while (from >= 0 && to <= s.Length - 1)
        {
            if (s[from] != s[to])
                break;
            from--;
            to++;
        }

        return from + 1 == to ? "" : s.Slice(from + 1, to - from - 1);
    }
}

Current Behavior

Runtime Error

Expected Behavior

Pass

On which platforms did you notice this

[ ] macOS
[x] Linux
[ ] Windows

Stacktrace

图片

The stacktrace text on LeetCode seems can't be copied. If you want to see it, you must do it yourself.


In case this is a LeetCode issue, I tried my code in Ubuntu vm. But this is my first time using mono, I encountered many errors like "couldn't found System.Memory" or "Could not load file or assembly System.Runtime.Loader".

So if you can compile and xunit test pass my following code, just close this issue.

Full Code
using System;
using Xunit;

namespace LongestPalindromicSubstring
{
    public interface ISolution { string LongestPalindrome(string s); }
    class Solution : ISolution
    {
        public string LongestPalindrome(string s) // BF
        {
            if (s.Length == 1)
                return s;
            var result = string.Empty.AsSpan();
            var span = s.AsSpan();
            for (int i = 0; i < s.Length - 1; i++)
                for (int j = i + 1; j <= s.Length; j++)
                {
                    var ss = span.Slice(i, j - i);
                    if (IsPalindromicString(ss) == true && ss.Length > result.Length)
                        result = ss;
                }
            return result.ToString();
        }
        internal bool IsPalindromicString(ReadOnlySpan<char> s)
        {
            if (s.Length == 1)
                return true;
            for (int i = 0; i < s.Length / 2; i++)
                if (s[i] != s[s.Length - i - 1])
                    return false;
            return true;
        }
    }

    class Solution2 : ISolution
    {
        public string LongestPalindrome(string s) // DP
        {
            ReadOnlySpan<char> ss = s.AsSpan();
            ReadOnlySpan<char> str = "";
            for (int i = 0; i < s.Length; i++)
            {
                var r = Expand(ss, i - 1, i + 1);
                if (r.Length > str.Length)
                    str = r;
                r = Expand(ss, i, i + 1);
                if (r.Length > str.Length)
                    str = r;
            }
            return str.ToString();
        }
        internal ReadOnlySpan<char> Expand(ReadOnlySpan<char> s, int from, int to) // 后两者表示将要评估的位置
        {
            while (from >= 0 && to <= s.Length - 1)
            {
                if (s[from] != s[to])
                    break;
                from--;
                to++;
            }

            return from + 1 == to ? "" : s.Slice(from + 1, to - from - 1);
        }
    }

    abstract
    public class MultiTest
    {
        protected virtual ISolution GetSo => new Solution2();

        [Theory]
        [InlineData("babad", "bab"), InlineData("cbbd", "bb"), InlineData("cbbb", "bbb")]
        [InlineData("a", "a"), InlineData("bb", "bb")]
        public void Test(string input, string expect)
        {
            var so = GetSo;
            string result = so.LongestPalindrome(input);
            Assert.Equal(expect, result);
        }
    }
    public class Test1 : MultiTest { protected override ISolution GetSo => new Solution(); }
    public class Test2 : MultiTest { protected override ISolution GetSo => new Solution2(); }

    public class BFTest
    {
        [Theory]
        [InlineData("bab", true), InlineData("bb", true)]
        [InlineData("baba", false)]
        [InlineData("a", true)]
        void IsPalindromicStringTest(string s, bool expect)
        {
            var so = new Solution();
            bool result = so.IsPalindromicString(s);
            Assert.Equal(expect, result);
        }
    }

    public class DPTest
    {
        [Theory]
        [InlineData("a", -1, 1), InlineData("bab", 0, 2),
        InlineData("bb", 0, 1), InlineData("abba", 1, 2)]
        void ExpandTest1(string s, int from, int to)
        {
            var so = new Solution2();
            string r = so.Expand(s, from, to).ToString();
            Assert.Equal(s, r);
        }
        [Fact]
        void ExpandTest2()
        {
            var so = new Solution2();
            string r = so.Expand("cb", 0, 1).ToString();
            Assert.Equal("", r);
        }
        [Fact]
        void ExpandTest3()
        {
            var so = new Solution2();
            string r = so.Expand("cbbb", 1, 2).ToString();
            Assert.Equal("bb", r);
        }
    }
}

But I would also appreciate it if you could tell me how to use mono run xunit.

Errors I encountered
nuget restore LeetCode.csproj
nuget install xunit.runner.console
msbuild /p:Configuration=Debug
mono ./xunit.runner.console.2.4.1/tools/netcoreapp2.0/xunit.console.dll ./bin/Debug/netcoreapp2.1/LeetCode.dll

System.IO.FileNotFoundException: Could not load file or assembly 'System.Runtime.Loader, Version=4.0.2.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a' or one of its dependencies.
File name: 'System.Runtime.Loader, Version=4.0.2.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a'
[ERROR] FATAL UNHANDLED EXCEPTION: System.IO.FileNotFoundException: Could not load file or assembly 'System.Runtime.Loader, Version=4.0.2.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a' or one of its dependencies.
File name: 'System.Runtime.Loader, Version=4.0.2.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a'

mono ./xunit.runner.console.2.4.1/tools/net472/xunit.console.exe ./bin/Debug/netcoreapp2.1/LeetCode.dll

xUnit.net Console Runner v2.4.1 (64-bit Desktop .NET 4.7.2, runtime: 4.0.30319.42000)
System.InvalidOperationException: Unknown test framework: could not find xunit.dll (v1) or xunit.execution.*.dll (v2) in /root/TEST/bin/Debug/netcoreapp2.1

msbuild /t:Publish
mono ./xunit.runner.console.2.4.1/tools/net472/xunit.console.exe ./bin/Debug/netcoreapp2.1/publish/LeetCode.dll

System.IO.FileNotFoundException : Could not load file or assembly 'System.Memory, Version=4.1.0.0, Culture=neutral, PublicKeyToken=cc7b13ffcd2ddd51' or one of its dependencies.
@imba-tjd imba-tjd changed the title Native Crash Report Runtime Error when using span on LeetCode Mar 22, 2019
@lewurm

This comment has been minimized.

Copy link
Member

@lewurm lewurm commented Mar 22, 2019

you can copy the stacktrace from the DOM:

Stacktrace:
/proc/self/maps:
00400000-00843000 r-xp 00000000 08:00 537488                             /usr/bin/mono-sgen
00a43000-00a49000 r--p 00443000 08:00 537488                             /usr/bin/mono-sgen
00a49000-00a4f000 rw-p 00449000 08:00 537488                             /usr/bin/mono-sgen
00a4f000-00ae0000 rw-p 00000000 00:00 0
00c1d000-00f54000 rw-p 00000000 00:00 0                                  [heap]
400ff000-4010f000 rwxp 00000000 00:00 0
40be5000-40c25000 rwxp 00000000 00:00 0
7fa10bdfa000-7fa10c000000 r--p 00000000 08:00 1186735                    /usr/lib/mono/gac/System.Data/4.0.0.0__b77a5c561934e089/System.Data.dll
7fa10c000000-7fa10c021000 rw-p 00000000 00:00 0
7fa10c021000-7fa110000000 ---p 00000000 00:00 0
7fa1101b2000-7fa1104ba000 r--p 00000000 08:00 1186820                    /usr/lib/mono/gac/System.Xml/4.0.0.0__b77a5c561934e089/System.Xml.dll
7fa1104ba000-7fa11059e000 r--p 00000000 08:00 1186778                    /usr/lib/mono/gac/System.Runtime.Serialization/4.0.0.0__b77a5c561934e089/System.Runtime.Serialization.dll
7fa11059e000-7fa110812000 r--p 00000000 08:00 1186821                    /usr/lib/mono/gac/System/4.0.0.0__b77a5c561934e089/System.dll
7fa110812000-7fa11081b000 ---p 00000000 00:00 0
7fa11081b000-7fa110a13000 rw-p 00000000 00:00 0
7fa110a13000-7fa110e6a000 r--p 00000000 08:00 748491                     /usr/lib/mono/4.5/mscorlib.dll
7fa110e6a000-7fa111e6a000 rw-p 00000000 00:00 0
7fa111e6a000-7fa111e6b000 ---p 00000000 00:00 0
7fa111e6b000-7fa112c00000 rw-p 00000000 00:00 0
7fa112c83000-7fa112d88000 r--p 00000000 08:00 1057588                    /usr/lib/mono/gac/System.Core/4.0.0.0__b77a5c561934e089/System.Core.dll
7fa112d88000-7fa112d93000 r-xp 00000000 08:00 397344                     /lib/x86_64-linux-gnu/libnss_files-2.23.so
7fa112d93000-7fa112f92000 ---p 0000b000 08:00 397344                     /lib/x86_64-linux-gnu/libnss_files-2.23.so
7fa112f92000-7fa112f93000 r--p 0000a000 08:00 397344                     /lib/x86_64-linux-gnu/libnss_files-2.23.so
7fa112f93000-7fa112f94000 rw-p 0000b000 08:00 397344                     /lib/x86_64-linux-gnu/libnss_files-2.23.so
7fa112f94000-7fa112f9a000 rw-p 00000000 00:00 0
Memory around native instruction pointer (0x40be772e):
0x40be771e  3e 00 00 00 48 8d 64 24 00 90 49 8b c5 49 8b ce  >...H.d$..I..I..
0x40be772e  48 63 09 89 08 49 8b c5 b9 04 00 00 00 48 63 c9  Hc...I.......Hc.
0x40be773e  48 83 c0 04 4c 8b e8 49 8b c6 b9 04 00 00 00 48  H...L..I.......H
0x40be774e  63 c9 48 83 c0 04 4c 8b f0 49 8b c7 83 e8 04 4c  c.H...L..I.....L
Native stacktrace:
mono run() [0x52018b]
mono run() [0x520488]
mono run() [0x4b407f]
mono run() [0x432ff2]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x11390) [0x7fa113bb9390]
[0x40be772e]

not exactly helpful unfortunately 😕 My best bet: It's a duplicate of #13452 It's also crashing in string manipulation and I expect that LeetCode is also hosted on AWS.

lewurm added a commit to lewurm/mono that referenced this issue Mar 22, 2019
We do 64bit operations, but operate on 32bit values. We need to sanitize those values.

Consider:
```
(lldb) x/8i 0x40011357
    0x40011357: 0f 84 c7 00 00 00  je     0x40011424
    0x4001135d: 49 8d 7c 24 14     leaq   0x14(%r12), %rdi
->  0x40011362: 49 8b c6           movq   %r14, %rax
    0x40011365: 48 d1 e0           shlq   %rax
    0x40011368: 48 03 f8           addq   %rax, %rdi
    0x4001136b: 0f b7 74 24 20     movzwl 0x20(%rsp), %esi
    0x40011370: 49 8b d7           movq   %r15, %rdx
    0x40011373: e8 bc 00 00 00     callq  0x40011434
(lldb) register read r14 rax rdi
     r14 = 0x0000000100000000
     rax = 0x0000000000000010
     rdi = 0x00007ffff7f48144
(lldb) si
(lldb) si
(lldb) si
(lldb) register read r14 rax rdi
     r14 = 0x0000000100000000
     rax = 0x0000000200000000
     rdi = 0x00008001f7f48144
```
In this snippet `r14` has some garbage in the 32bit upper half, which unfortunately is taken into account for the multiplication (`shl`) and addition in order to compute the address (`rdi`).

Several factors why we didn't see it earlier:
1. It doesn't trigger on AOT, because when compiling mscorlib.dll, `Unsafe.dll` isn't available to the AOT compiler and thus inlining won't happen. We use AOT where possible in our CI. When doing a call the upper halfs are properly cleared.
2. It doesn't trigger on macOS due to different memory organization.  We don't end up with gargabe in the registers.
3. Recently we added intrinsics for Unsafe.* https://github.com/mono/mono/pull/12605/files#diff-89fe30e1e87c5db21be052ddb0c8e28dR329 It masks this specific problem. Funnily enough, the assumed IL for the `Add ()` intrinsics didn't match what we had before. Now it does :-)

Fixes mono#13452 and mono#13597
monojenkins added a commit to monojenkins/mono that referenced this issue Mar 22, 2019
We do 64bit operations, but operate on 32bit values. We need to sanitize those values.

Consider:
```
(lldb) x/8i 0x40011357
    0x40011357: 0f 84 c7 00 00 00  je     0x40011424
    0x4001135d: 49 8d 7c 24 14     leaq   0x14(%r12), %rdi
->  0x40011362: 49 8b c6           movq   %r14, %rax
    0x40011365: 48 d1 e0           shlq   %rax
    0x40011368: 48 03 f8           addq   %rax, %rdi
    0x4001136b: 0f b7 74 24 20     movzwl 0x20(%rsp), %esi
    0x40011370: 49 8b d7           movq   %r15, %rdx
    0x40011373: e8 bc 00 00 00     callq  0x40011434
(lldb) register read r14 rax rdi
     r14 = 0x0000000100000000
     rax = 0x0000000000000010
     rdi = 0x00007ffff7f48144
(lldb) si
(lldb) si
(lldb) si
(lldb) register read r14 rax rdi
     r14 = 0x0000000100000000
     rax = 0x0000000200000000
     rdi = 0x00008001f7f48144
```
In this snippet `r14` has some garbage in the 32bit upper half, which unfortunately is taken into account for the multiplication (`shl`) and addition in order to compute the address (`rdi`).

Several factors why we didn't see it earlier:
1. It doesn't trigger on AOT, because when compiling mscorlib.dll, `Unsafe.dll` isn't available to the AOT compiler and thus inlining won't happen. We use AOT where possible in our CI. When doing a call the upper halfs are properly cleared.
2. It doesn't trigger on macOS due to different memory organization.  We don't end up with gargabe in the registers.
3. Recently we added intrinsics for Unsafe.* https://github.com/mono/mono/pull/12605/files#diff-89fe30e1e87c5db21be052ddb0c8e28dR329 It masks this specific problem. Funnily enough, the assumed IL for the `Add ()` intrinsics didn't match what we had before. Now it does :-)

Fixes mono#13452 and mono#13597
monojenkins added a commit to monojenkins/mono that referenced this issue Mar 22, 2019
We do 64bit operations, but operate on 32bit values. We need to sanitize those values.

Consider:
```
(lldb) x/8i 0x40011357
    0x40011357: 0f 84 c7 00 00 00  je     0x40011424
    0x4001135d: 49 8d 7c 24 14     leaq   0x14(%r12), %rdi
->  0x40011362: 49 8b c6           movq   %r14, %rax
    0x40011365: 48 d1 e0           shlq   %rax
    0x40011368: 48 03 f8           addq   %rax, %rdi
    0x4001136b: 0f b7 74 24 20     movzwl 0x20(%rsp), %esi
    0x40011370: 49 8b d7           movq   %r15, %rdx
    0x40011373: e8 bc 00 00 00     callq  0x40011434
(lldb) register read r14 rax rdi
     r14 = 0x0000000100000000
     rax = 0x0000000000000010
     rdi = 0x00007ffff7f48144
(lldb) si
(lldb) si
(lldb) si
(lldb) register read r14 rax rdi
     r14 = 0x0000000100000000
     rax = 0x0000000200000000
     rdi = 0x00008001f7f48144
```
In this snippet `r14` has some garbage in the 32bit upper half, which unfortunately is taken into account for the multiplication (`shl`) and addition in order to compute the address (`rdi`).

Several factors why we didn't see it earlier:
1. It doesn't trigger on AOT, because when compiling mscorlib.dll, `Unsafe.dll` isn't available to the AOT compiler and thus inlining won't happen. We use AOT where possible in our CI. When doing a call the upper halfs are properly cleared.
2. It doesn't trigger on macOS due to different memory organization.  We don't end up with gargabe in the registers.
3. Recently we added intrinsics for Unsafe.* https://github.com/mono/mono/pull/12605/files#diff-89fe30e1e87c5db21be052ddb0c8e28dR329 It masks this specific problem. Funnily enough, the assumed IL for the `Add ()` intrinsics didn't match what we had before. Now it does :-)

Fixes mono#13452 and mono#13597
@marek-safar marek-safar added this to the 2018-08 (5.18.xx) milestone Mar 22, 2019
monojenkins added a commit to monojenkins/mono that referenced this issue Mar 22, 2019
We do 64bit operations, but operate on 32bit values. We need to sanitize those values.

Consider:
```
(lldb) x/8i 0x40011357
    0x40011357: 0f 84 c7 00 00 00  je     0x40011424
    0x4001135d: 49 8d 7c 24 14     leaq   0x14(%r12), %rdi
->  0x40011362: 49 8b c6           movq   %r14, %rax
    0x40011365: 48 d1 e0           shlq   %rax
    0x40011368: 48 03 f8           addq   %rax, %rdi
    0x4001136b: 0f b7 74 24 20     movzwl 0x20(%rsp), %esi
    0x40011370: 49 8b d7           movq   %r15, %rdx
    0x40011373: e8 bc 00 00 00     callq  0x40011434
(lldb) register read r14 rax rdi
     r14 = 0x0000000100000000
     rax = 0x0000000000000010
     rdi = 0x00007ffff7f48144
(lldb) si
(lldb) si
(lldb) si
(lldb) register read r14 rax rdi
     r14 = 0x0000000100000000
     rax = 0x0000000200000000
     rdi = 0x00008001f7f48144
```
In this snippet `r14` has some garbage in the 32bit upper half, which unfortunately is taken into account for the multiplication (`shl`) and addition in order to compute the address (`rdi`).

Several factors why we didn't see it earlier:
1. It doesn't trigger on AOT, because when compiling mscorlib.dll, `Unsafe.dll` isn't available to the AOT compiler and thus inlining won't happen. We use AOT where possible in our CI. When doing a call the upper halfs are properly cleared.
2. It doesn't trigger on macOS due to different memory organization.  We don't end up with gargabe in the registers.
3. Recently we added intrinsics for Unsafe.* https://github.com/mono/mono/pull/12605/files#diff-89fe30e1e87c5db21be052ddb0c8e28dR329 It masks this specific problem. Funnily enough, the assumed IL for the `Add ()` intrinsics didn't match what we had before. Now it does :-)

Fixes mono#13452 and mono#13597
monojenkins added a commit that referenced this issue Mar 25, 2019
[amd64] use 32bit variant of lea_membase for 32bit operations

Consider
```
 xor %r15, %r15       // %r15 = 0x0
 dec %r15d            // %r15 = 0xffff_ffff
 lea 0x1(%r15), %rdx  // %rdx = 0x1_0000_0000 but should be 0x0
```

instead `lea 0x1(%r15), %edx` should be generated.


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