Segmentation Fault chkstk_ms C++

Question

I need help with this following counting sort implementation. Is it because value of x can be too big? I am getting segmentation fault. This is what gdb says:

Program received signal SIGSEGV, Segmentation fault.
___chkstk_ms () at /usr/src/debug/gcc-5.4.0- 1/libgcc/config/i386/cygwin.S:146
146     /usr/src/debug/gcc-5.4.0-1/libgcc/config/i386/cygwin.S: No such file or directory.

And here is the code snippet,

void radix_sort::sort_array(int array[], int n)
{
    int arrayB[n];

    auto k = *std::max_element(&array[0], &array[n - 1]);
    auto m = *std::min_element(&array[0], &array[n - 1]);

    long int x = k - m + 1;
    int arrayC[x];

    for (auto i = 0; i < n; i++)
        arrayC[array[i] - m]++;

    for (long int i = 1; i < x; i++)
        arrayC[i] = arrayC[i] + arrayC[i - 1];

    for (auto i = n - 1; i >= 0; i--)
    {
        arrayB[arrayC[array[i] - m] - 1] = array[i];
        arrayC[array[i] - m]--;
    }

    for (int i = 0; i < n; i++)
        array[i] = arrayB[i];
}

`int arrayB[n];` is non-standard C++ and in the GCC 4 and 5 implementation can easily result in a stack overflow if `n` is sufficiently large. Probably not your problem, but worth keeping an eye on. same again for `int arrayC[x];`. Search keyword: "Variable Length Array" for more info. — user4581301, Aug 09 '16 at 05:36
The job of `__chkstk_ms` is to *intentionally* generate a segfault when the array cannot fit on the stack. So yes, `n` is too large. If you can't limit its value then you must use the new[] and delete[] operators instead. — Hans Passant, Aug 09 '16 at 06:51
I tried using new[] and delete[] operators. It is not segfaulting anymore. gdb now says the problem is with this line int arrayC[x]; I know x can be very big. Consider if k = 2 billion and m = -2 billion, then x = 4 billion. What should I use to make sure it works with this range? — ARSN, Aug 09 '16 at 07:17

score 0 · Answer 1 · answered Aug 09 '16 at 05:43

0

In

arrayC[array[i] - m]++;

at this point in the code no elements of arrayC have been assigned, so an unknown number is incremented. This may blow up

arrayB[arrayC[array[i] - m] - 1] = array[i];

a few lines later because arrayC[array[i] - m] could be negative or a few billion and out of range for all we know.

answered Aug 09 '16 at 05:43

user4581301

33,082
7
33
54

How do you suggest to fix it? – ARSN Aug 09 '16 at 05:58
My go-to would be to replace the variable length arrays with [`std::vector`](http://en.cppreference.com/w/cpp/container/vector). `std::vector arrayC(x);` would make `arrayC` standard-compliant and auto initialize all elements to 0. If `std::vector` is off the table (and variable length arrays aren't for some reason), `int arrayC[n] = {0};`. Otherwise [`std::fill`](http://en.cppreference.com/w/cpp/algorithm/fill) or similar. – user4581301 Aug 09 '16 at 06:09
I am still getting the same seg fault using int arrayC[x] = {0}; I have another version with vector which does not give any output here: http://stackoverflow.com/questions/38840961/counting-sort-c11 – ARSN Aug 09 '16 at 06:32

Vlad from Moscow · Answer 2 · 2023-04-01T11:57:51.337

These declarations of arrays

int arrayB[n];
int arrayC[x];

declares variable length arrays. Variables length arrays are not a standard C++ feature. Instead of declaring variable length arrays you need to allocate memory dynamically.

These calls of standard algorithms

auto k = *std::max_element(&array[0], &array[n - 1]);
auto m = *std::min_element(&array[0], &array[n - 1]);

ignore the last element of the array array. Instead you need to write

auto k = *std::max_element( array, array + n );
auto m = *std::min_element( array, array + n );

The array arrayC is not initialized.

int arrayC[x];

So this statement

arrayC[array[i] - m]++;

invokes undefined behavior.

Pay attention to that within the function you need to check that n is greater than 0.

The function can be declared and defined the following way.

void radix_sort::sort_array( int a[], size_t n )
{
    if (n)
    {
        auto minmax = std::minmax_element( a, a + n );
        auto min = *minmax.first, max = *minmax.second;

        size_t k = max - min + 1;

        auto p = std::make_unique<int[]>( k );

        for (size_t i = 0; i < n; i++)
        {
            ++p[a[i] - min];
        }

        std::partial_sum( p.get(), p.get() + k, p.get() );

        auto b = std::make_unique<int[]>( n );

        for (size_t i = n; i-- != 0; )
        {
            b[--p[a[i] - min]] = a[i];
        }

        std::copy( b.get(), b.get() + n, a );
    }
}

Segmentation Fault chkstk_ms C++

2 Answers2

Linked