CODEWITHSUNDEEP
cruntime-error
Mr.Barbo
Mr.Barbo

Reputation: 69

stack corruption by eliminate a printf()

some time ago I tried to program a Mergesort. In some point I got an error that I was able to solve, but still saved the code because have something strange that i don't understand. The code is the following:

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

typedef int elem;

void mergesort(elem * arr, unsigned n){
    if(n != 1){
        if(n == 2){
            if(arr[0] > arr[1]){
                int change = arr[0];
                arr[0] = arr[1];
                arr[1] = change;
            }
        }else{
            unsigned i = 0, j = 0, mit = (n+1)>>2, fin = n>>2;
            elem * arr_2 = (elem *)malloc(sizeof(elem) * n), * mit_arr = arr+mit;
            mergesort(arr, mit);
            mergesort(mit_arr, fin);
            while(i < mit || j < fin){
                if(arr[i] <= mit_arr[j]){
                    arr_2[j+i] = arr[i];
                    i++;
                }else{
                    arr_2[j+i] = mit_arr[j];
                    j++;
                }
            }
            for(i=0; i<n; i++)
                arr[i] = arr_2[i];
            free(arr_2);
        }
    }
}

int main(){
    unsigned a = 10;
    int i;
    elem * arr = (elem*)malloc(sizeof(elem) * a);
    arr[0] = 12;
    arr[1] = 3;
    arr[2] = -3;
    arr[3] = 22;
    arr[4] = 12;
    arr[5] = 11;
    arr[6] = 4;
    arr[7] = 9;
    arr[8] = 10;
    arr[9] = 2;
    printf("something\n");     // 1
    mergesort(arr, a);
    printf("\n");
    for(i=0; i<a; i++){
        printf("%d, ", arr[i]);
    }
    printf("\n");
    free(arr);
    return 0;
}

The thing is that, despite the fact that the code doesn't do what I want and it seems like there is no error, if I comment out the line marked by 1 (printf("something\\n"); ) then the error "malloc(): corrupted top size" appears. I actually don't know why something like that is possible, so I came here to see if someone have an explanation.

I tried to debug the program with gdb and got the same error, but have more information:

Program received signal SIGABRT, Aborted.
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
50  ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.

but still without idea of what happened.

Upvotes: 1

Views: 134

Answers (1)

paddy
paddy

Reputation: 63471

There are a couple of major issues with your code. These are things you should be able to test yourself by checking whether the values being used by your function are what you expect.

Here's the first issue. You have calculated the length of the first half of the array as (n+1)>>2, and then you assume the length of the remaining array is n>>2. That is simply not true. Shifting a value to the right by 2 binary places is a division by four.

It is far better to use "normal" math instead of attempting to be clever. This reduces the chance for errors, and makes your code easier to read.

unsigned mit = n / 2, fin = n - mit;

The other issue is your merge. You have made your while-loop run until both i and j are out-of-range. But in your loop, it's guaranteed that on at least one of the iterations, one of those values will be out-of-range.

A better way to merge arrays uses three loops. The first one runs until either of the arrays has been merged in, and the remaining two loops will copy the remaining part of the other array.

unsigned x = 0, i = 0, j = 0;
while(i < mit && j < fin){
    if(arr[i] <= mit_arr[j]){
        arr_2[x++] = arr[i++];
    }else{
        arr_2[x++] = mit_arr[j++];
    }
}
while(i < mit){
    arr_2[x++] = arr[i++];
}
while(j < fin){
    arr_2[x++] = mit_arr[j++];
}

Upvotes: 2

Related Questions