Do not use stackalloc inside of a loop

[terrajobst]

Calling stackalloc in a loop leads to stack overflow. This bug is easy to introduce with the above.

Category: Performance

Examples of patterns to report on

For loop, iteration count is non-constant

private int SomeMethod(ReadOnlySpan<byte> source, Span<byte> destination)
{
    int writeOffset = 0;

    for (int i = 0; i < source.Length; i += ChunkSize)
    {
        Span<byte> tmp = stackalloc byte[32];
        writeOffset += CRC32(
            source.Slice(i, Math.Min(source.Length - i, ChunkSize)),
            tmp);

        WriteReversed(tmp, destination.Slice(writeOffset));
    }

    return writeOffset;
}

While loop, non-constant iteration count:

private int SomeMethod(ReadOnlySpan<byte> source, Span<byte> destination)
{
    int writeOffset = 0;

    while (!source.IsEmpty)
    {
        Span<byte> tmp = stackalloc byte[32];
        ReadOnlySpan<byte> cur = source.Length < ChunkSize ? source : source.Slice(0, ChunkSize);

        writeOffset += CRC32(cur, tmp);
        WriteReversed(tmp, destination.Slice(writeOffset));
        source = source.Slice(cur.Length);
    }

    return writeOffset;
}

(Also do/while, and foreach)

Examples of patterns to not report on

This method always has the same sized stackalloc.
It could be used more efficiently, but it's deterministic, so it's not worth reporting on.

private int SomeMethod(ReadOnlySpan<byte> source, Span<byte> destination)
{
    for (int i = 0; i < 4; i++)
    {
        Span<byte> tmp = stackalloc byte[32];
        CRC32(source.Slice(i), tmp);
        WriteReversed(tmp, destination.Slice(i));
    }

    return 35;
}

Stackalloc is in a loop, but it only ever runs on one iteration:

private int SomeMethod(ReadOnlySpan<byte> source, Span<byte> destination)
{
    for (int i = 1; i < source.Length; i++)
    {
        if (source[i - 1] + source[i] > 202)
        {
            Span<byte> tmp = stackalloc byte[32];
            CRC32(source.Slice(i+1), tmp);
            WriteReversed(tmp, destination);
            return 32;
        }
    }

    return 0;
}

Same idea, different shape.

private int SomeMethod(Span<byte> destination)
{
    int accum = 0;

    while (true)
    {
        ReadOnlySpan<byte> next = GetNextData();

        for (int i = 0; i < next.Length; i++)
        {
            accum += next[i];
        }

        int popCount = PopCount(accum);

        if (popCount > 2 && popCount < 6)
        {
            if (_reversed)
            {
                Span<byte> tmp = stackalloc byte[32];
                CRC32(accum.AsBytes(), tmp);
                WriteReversed(tmp, destination);
            }
            else
            {
                CRC32(accum.AsBytes(), destination);
            }

            break;
        }
    }

    return 32;
}

[jeffhandley]

Estimates:

• Analyzer: Medium
• Fixer: Not Applicable

[jeffhandley]

Look for loops that don't use a literal to define the bounds of the loop. But, there are false-positive scenarios like a block that performs a stackalloc and then breaks. Those scenarios need to be designed out to capture what we'd flag and what we wouldn't.

[jeffhandley]

Suggestion for approach:

1. Write the simple rule
2. Run it on dotnet/runtime
3. Review occurrences to guide the detailed design of this analyzer and determine what severity we want to aim for and if this analyzer would be on by default

[stephentoub]

I'd still warn on the first example in the not-report-on section, where it's executing the stackalloc a fixed number of times. Moving the stackalloc out of the loop is better, and even with a fixed count, what heuristic would we include to validate the limit? If I iterated a million times, but still with a fixed upper bound, that's not going to work well.

I'd be ok if we started on this one just always warning if we detected the stackalloc was inside a loop of any kind, and see how many false positives we hit upon in dotnet/runtime, dotnet/aspnetcore, and dotnet/roslyn.