malloc: Incorrect checksum for freed object

user_5299289 0
Viewed 2149

Below is function to do merge sort. but I meet error when I execute. The allocated memory(aux) has been freed every time in function merge, why it will be modified after freed?

a.out(65287,0x1112bedc0) malloc: Incorrect checksum for freed object
0x7ff9a4c05888: probably modified after being freed. Corrupt value:
0xb00000003 a.out(65287,0x1112bedc0) malloc: *** set a breakpoint in
malloc_error_break to debug Abort trap: 6

void merge(int arr[], int lo, int mid, int hi) {
    int i = lo; 
    int j = mid + 1;
    int *aux = (int *)malloc((hi - lo + 1) * sizeof(int));
    for (int k = lo; k <= hi; k++) {
        aux[k] = arr[k];
    }   
    for (int k = lo; k <= hi; k++) {
        if (i > mid)
            arr[k] = aux[j++];
        else if (j > hi)
            arr[k] = aux[i++];
        else if (aux[i] > aux[j])
            arr[k] = aux[j++];
        else
            arr[k] = aux[i++];
    } 
    free(aux);
}

void mergesort1(int arr[], int lo, int hi) {
    if (lo >= hi)
        return;
    int mid = lo + (hi - lo) / 2;
    mergesort1(arr, lo, mid);
    mergesort1(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
}

call with:

mergesort1(arr, 0, 9);
mergesort malloc recursion c
2 Answers

malloc((hi - lo + 1) * sizeof(int)) allocates space for elements indexed from 0 to hi-lo, but for (int k = lo; k <= hi; k++) … aux[k] = … accesses the elements with indices from lo to hi, thus writing outside the allocated memory.

user_2982250

The aux array is not initialized properly: for (int k = lo; k <= hi; k++) { aux[k] = arr[k]; } should be:

    for (int k = lo; k <= hi; k++) {
        aux[k -lo] = arr[k];
    }

Your code writes beyond the end of the allocated array, potentially causing corruption of the data used by malloc() and free() to keep track of allocated memory.

Note that i and j should also be initialized differently and it is confusing to include the upper bound in the merge sort algorithm. If hi is excluded, the code is simpler as no +1/-1 adjustments are necessary:

void merge1(int arr[], int lo, int mid, int hi) {
    int i = 0; 
    int j = mid -= lo;
    int n = hi - lo;
    int *aux = (int *)malloc(n * sizeof(int));
    for (int k = 0; k < n; k++) {
        aux[k] = arr[lo + k];
    }   
    for (int k = lo; k < hi; k++) {
        if (i >= mid)
            arr[k] = aux[j++];
        else if (j >= n)
            arr[k] = aux[i++];
        else if (aux[i] > aux[j])
            arr[k] = aux[j++];
        else
            arr[k] = aux[i++];
    } 
    free(aux);
}

void mergesort1(int arr[], int lo, int hi) {
    if (hi - lo < 2)
        return;
    int mid = lo + (hi - lo) / 2;
    mergesort1(arr, lo, mid);
    mergesort1(arr, mid, hi);
    merge1(arr, lo, mid, hi);
}

call with: mergesort1(arr, 0, 10);, which is simpler because 10 is the array length.

The code can be further simplified using pointer arithmetic:

void merge2(int arr[], int mid, int hi) {
    int *aux = malloc(n * sizeof(*aux));
    for (int i = 0; i < n; i++) {
        aux[i] = arr[i];
    }   
    for (int i = 0, j = mid, k = 0; i < mid;) {
        if (j >= n || aux[i] <= aux[j])
            arr[k++] = aux[i++];
        else
            arr[k++] = aux[j++];
    } 
    free(aux);
}

void mergesort2(int arr[], int n) {
    if (n < 2)
        return;
    int mid = n / 2;
    mergesort2(arr, mid);
    mergesort2(arr + mid, n - mid);
    merge2(arr, mid, n);
}

call with: mergesort2(arr, 10);, where 10 is the array length.

user_45932670
Related