'malloc(): corrupted top size' After allocating more than 200K int

Question

I got assignment to do Bucket Sort with openMP, and I decided to do Quick Sort on each bucket. The requirement wants me to test by keep increasing the amount of integers and change the number of thread until reaching 1 million integers with 16 threads.

Here's my code in C:

#include <stdio.h>
#include <omp.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;

}

int partition(int arr[], int low, int high) {

    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {

        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }

    }

    swap(&arr[i + 1], &arr[high]);

    return (i + 1);
}

void quickSort(int arr[], int low, int high) {

    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }

}

int main(int argc, char* argv[]) {

    //Check arguments
    if (argc > 3 || argc < 3) {
        fprintf(stderr, "Error: Invalid arguments. This program require 2 arguments.\nUsage: ./bucketSort <thread number> <amount of random number>\n");
        return 1;
    }

    printf("Random seed");

    //Initialize random seed
    srand((unsigned)time(NULL));

    int threadNum = atoi(argv[1]);
    int randomTime = atoi(argv[2]);

    int* numArr = (int*)malloc(randomTime * sizeof(int));

    if(numArr == NULL){
        fprintf(stderr, "Error: Unable to allocate memory.");
        return 1;
    }

    printf("\nStart random");

    //Since RAND_MAX is limited to 0x7FFF (32,767), so we need to get creative to random beyond RAND_MAX
    for (int i = 0; i < randomTime; i++) {

        int rand1 = rand();
        int rand2 = rand();
        int rand3 = rand();

        int combinedRandom = ((rand1 % 100) * 1000) + ((rand2 % 100) * 10) + (rand3 % 10);

        numArr[i] = combinedRandom;

    }

    printf("\nFinished Random");

    double timeSpent = 0;

    int rangePerBucket = ceil(99999 / threadNum);

    int* outputArr = (int*)malloc(randomTime * sizeof(int));

    int* groupMemberCount = (int*)malloc(threadNum * sizeof(int));

    if(outputArr == NULL || groupMemberCount == NULL){
        fprintf(stderr, "Error: Unable to allocate memory.");
        return 1;
    }

    clock_t begin = clock();

    printf("\nStart parallel section.");

    #pragma omp parallel shared(numArr, outputArr, groupMemberCount) num_threads(threadNum)
    {

        int myID = omp_get_thread_num();
        int totalThread = omp_get_num_threads();

        int beginRange = myID * rangePerBucket;
        int endRange = (myID + 1) * rangePerBucket - 1;

        int* temp = (int*)omp_alloc(rangePerBucket * sizeof(int), omp_large_cap_mem_alloc);

        if( temp == NULL ){
            fprintf(stderr, "Error: Thread %d is unable to allocate memory.", myID);

        }

        int memberCount = 0;

        //Put in bucket
        for (int j = 0; j < randomTime; j++)
        {
            if (numArr[j] >= beginRange && numArr[j] <= endRange) {
                temp[memberCount] = numArr[j];
                memberCount++;
            }
        }

        groupMemberCount[myID] = memberCount;

        int* myGroup = (int*)omp_alloc(memberCount * sizeof(int), omp_large_cap_mem_alloc);

        if( myGroup == NULL ){
            fprintf(stderr, "Error: Thread %d is unable to allocate memory.", myID);
        }

        for (int i = 0; i < memberCount; i++) {
            myGroup[i] = temp[i];
        }

        //Sort
        quickSort(myGroup, 0, memberCount - 1);
        printf("\nThread %d of %d has finished sorting.", myID, totalThread);

        //Find the start of output array
        int startIndex = 0;
        for( int i = 0; i < myID; i++ ){
            startIndex += groupMemberCount[i];
        }

        //Combine array
        for (int k = 0; k < memberCount; k++) {

            outputArr[startIndex + k] = myGroup[k];

        }

        printf("\nArray from thread %d has combined.", myID);

        omp_free(myGroup, omp_large_cap_mem_alloc);
        omp_free(temp, omp_large_cap_mem_alloc);
    }

    free(numArr);
    free(outputArr);
    free(groupMemberCount);

    clock_t end = clock();

    timeSpent = (double)(end - begin) / CLOCKS_PER_SEC;

    printf("\nTime spent sorting: %f seconds.\n", timeSpent);

    return 0;
}

I compiled it with gcc -fopenmp ./bucketSort.c -o ./bucketSort. Everything runs fine until I start testing with 100K integers (I wrote 200K in the topic because my program allocate it twice). The program immediately return malloc(): corrupted top size after printing Finished Random (so the first 100K in numArr is fine?). This is the first time I used malloc() and omp_alloc(), so feel free to correct me if I've done something wrong. I'm running this code in Ubuntu WSL btw.

What I've tried:

• I tried calloc() but the result is the same, error after 2nd calloc().
• I tried increase ulimit to unlimit.

Answer 1

Usually, valgrind or -fsanitize=address give good diagnostics for such errors.

Compiling and linking with -fsanitize=address shows that there is a heap overflow on this line:

                temp[memberCount] = numArr[j];

The memberCount variable is equal to rangePerBucket at this point. Both are one less than randomTime. But the temp array has only rangePerBucket elements, so that index is out of range.