2

I have been implementing vanilla version of a merge sort in C. In a sorting section itself, which is a separate function, I created a temporary array via malloc, like this:

int *tmp_arr = malloc(sizeof *tmp_arr * (end - strt));

For some reason I'm getting invalid reads and writes throughout all the temporary array while trying to fill it with elements after comparisons. int tmp_arr[end - strt]; works fine.

Why am I writing outside of a heap (and what is happening if my current understanding is incorrect)?

Below are the functions where malloc is used, extract from valgrind output and exact mistake I am getting upon execution. I didn't forget to free stuff.

I got my initial array hardcoded as I wanted to write the stuff and bother with inputs afterwards.

This particular array { 8, 1, 10, 54, 2, 0, -3, 5, 70, 60, 11, 4 } has the maximum length where I can have my program running, if longer - program crashes with the mistake described at the very end of the post. Valgrind output is always the same in principle, the longer the array is, the more read and write mistakes I am getting.

Program:

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

void merge_sort(int *arr, int strt, int end);
void merge(int *arr, int strt, int mid, int end);

void print_arr(int *arr, int arr_len);

int main(void) {
  int arr[] = { 8, 1, 10, 54, 2, 0, -3, 5, 70, 60, 11, 4 };
  int arr_len = sizeof(arr) / sizeof(arr[0]); 
  print_arr(arr, arr_len);
  merge_sort(arr, 0, arr_len - 1);
  print_arr(arr, arr_len);
}

void print_arr(int *arr, int arr_len) {
  for (int i = 0; i < arr_len; i++) {
    printf("%i ", arr[i]);
  }
  printf("\n");
}

void merge_sort(int *arr, int strt, int end) {
  if (strt < end) {
    int mid = (end + strt) / 2;
    merge_sort(arr, strt, mid);
    merge_sort(arr, mid + 1, end);
    merge(arr, strt, mid, end); 
  }
}

void merge(int *arr, int strt, int mid, int end) {
  int *tmp_arr = malloc(sizeof *tmp_arr * (end - strt));
  //int tmp_arr[end - strt];
  int i = strt;
  int j = 0;
  int k = mid + 1;
  while ((i <= mid) && (k <= end)) {
    if (arr[i] < arr[k]) {
      tmp_arr[j] = arr[i];
      i++;
      j++;   
    }
    else {
      tmp_arr[j] = arr[k];
      k++;
      j++; 
    }
  }
  while(i <= mid) {
      tmp_arr[j] = arr[i];
      j++;
      i++;
  }
  while (k <= end) {
      tmp_arr[j] = arr[k];
      j++;
      k++;
  }
  for (int m = 0; m < j; m++) {
    arr[strt + m] = tmp_arr[m];
  }
  free(tmp_arr);
}

Extract from valgrind output with the array hardcoded above:

 valgrind ./main==355== Memcheck, a memory error detector
==355== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.==355== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright inf
o
==355== Command: ./main==355== 
8 1 10 54 2 0 -3 5 70 60 11 4 ==355== Invalid write of size 4
==355==    at 0x108A40: merge (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x108917: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x108823: main (in /home/runner/MiniatureEarnestSecurity/ma
in)
==355==  Address 0x522d484 is 0 bytes after a block of size 4 alloc'd==355==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-
amd64-linux.so)==355==    by 0x108943: merge (in /home/runner/MiniatureEarnestSecurity/m
ain)
==355==    by 0x108917: merge_sort (in /home/runner/MiniatureEarnestSecur
ity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecur
ity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecur
ity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecur
ity/main)
==355==    by 0x108823: main (in /home/runner/MiniatureEarnestSecurity/ma
in)
==355== 
==355== Invalid read of size 4
==355==    at 0x108AC8: merge (in /home/runner/MiniatureEarnestSecurity/m
ain)
==355==    by 0x108917: merge_sort (in /home/runner/MiniatureEarnestSecur
ity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x108823: main (in /home/runner/MiniatureEarnestSecurity/main)
==355==  Address 0x522d484 is 0 bytes after a block of size 4 alloc'd
==355==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==355==    by 0x108943: merge (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x108917: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x1088EB: merge_sort (in /home/runner/MiniatureEarnestSecurity/main)
==355==    by 0x108823: main (in /home/runner/MiniatureEarnestSecurity/main)
==355== 
            
            //repeating till the end
            
        -3 0 1 2 4 5 8 10 11 54 60 70 
        ==355== 
        ==355== HEAP SUMMARY:
        ==355==     in use at exit: 0 bytes in 0 blocks
        ==355==   total heap usage: 12 allocs, 12 frees, 1,156 bytes allocated
        ==355== 
        ==355== All heap blocks were freed -- no leaks are possible
        ==355== 
        ==355== For counts of detected and suppressed errors, rerun with: -v
        ==355== ERROR SUMMARY: 22 errors from 16 contexts (suppressed: 0 from 0)

Mistake that I'm getting upon execution:

main: malloc.c:2401: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inus e (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed. exited, aborted

5
  • 3
    Please post a minimal reproducible example in your question, not in an external link. Aug 12, 2020 at 19:52
  • Ok, got it, done. Aug 12, 2020 at 20:01
  • I guess i fixed the cause of closure, would be nice if it could be reopened. Aug 12, 2020 at 20:08
  • @AntonTretyakov, it still does not follow MRE guidelines, namely the reproducilble part, post the test case(s) you used for the function. We can see the array but not the values you passed to the other parameters, my bet goes to corrupted memory by way of overflow or underflow of the buffer. Using the stack accesses out-of-bounds can be more forgiving than accessing unallocated memory, though still undefined behavior.
    – anastaciu
    Aug 12, 2020 at 22:01
  • @anastaciu, ok, got it, added the whole text and a few words in array. I got my initial array hardcoded as i wanted to write the stuff and bother with inputs afterwards. This particular array { 8, 1, 10, 54, 2, 0, -3, 5, 70, 60, 11, 4 } has the maximum length where i can have my program running, if longer - program crashes with the mistake described at the very end of the post. Valgrind output is always the same in principle, the longer the array is, the more read and write mistakes i m getting. Aug 13, 2020 at 19:39

1 Answer 1

1

The problem is the length of the slice to sort is not end - strt but end - strt + 1 as you are using the error prone convention to include the end element.

The allocation should be int *tmp_arr = malloc(sizeof *tmp_arr * (end - strt + 1));

The reason the code seems to work with the array declared locally with automatic storage is pure chance. You still have undefined behavior when storing data to tmp_arr[end - strt] but it just so happens that it does not seem to have any adverse side effect, whereas when you do so with the allocated object, you probably corrupt the internal data used by malloc() to keep track of allocated block, which gets detected by the allocation routines or a consistency check performed by valgrind.

It is very error prone to include the index to the last element in the slice. I wish this nonsense would no longer be taught in programming classes for any language with 0 based array indexes. It requires many confusing +1/-1 adjustments in the code whereas using the index to the element after the last one allows for simpler code.

Here is a modified version:

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

void merge_sort(int *arr, int strt, int end);
void merge(int *arr, int strt, int mid, int end);
void print_arr(int *arr, int arr_len);

int main(void) {
  int arr[] = { 8, 1, 10, 54, 2, 0, -3, 5, 70, 60, 11, 4 };
  int arr_len = sizeof(arr) / sizeof(arr[0]); 
  print_arr(arr, arr_len);
  merge_sort(arr, 0, arr_len);
  print_arr(arr, arr_len);
}

void print_arr(int *arr, int arr_len) {
  for (int i = 0; i < arr_len; i++) {
    printf("%i ", arr[i]);
  }
  printf("\n");
}

void merge_sort(int *arr, int strt, int end) {
  if (end - strt > 1) {
    // avoid potential arithmetic overflow on start+end
    int mid = strt + (end - strt) / 2;
    merge_sort(arr, strt, mid);
    merge_sort(arr, mid, end);
    merge(arr, strt, mid, end); 
  }
}

void merge(int *arr, int strt, int mid, int end) {
  int *tmp_arr = malloc(sizeof(*tmp_arr) * (end - strt));
  //int tmp_arr[end - strt];
  int i = strt;
  int j = 0;
  int k = mid;
  while (i < mid && k < end) {
    if (arr[i] <= arr[k]) {
      tmp_arr[j++] = arr[i++];
    } else {
      tmp_arr[j++] = arr[k++];
    }
  }
  while (i < mid) {
      tmp_arr[j++] = arr[i++];
  }
  // copying the remaining elements from the right half is not needed as they
  // are already in the proper place
  //while (k < end) {
  //    tmp_arr[j++] = arr[k++];
  //}
  for (int m = 0; m < j; m++) {
    arr[strt + m] = tmp_arr[m];
  }
  free(tmp_arr);
}
15
  • You beat me to it.
    – anastaciu
    Aug 13, 2020 at 19:56
  • I will shame myself for the rest of the week for such a miscalculation.Thank you for your help! Aug 13, 2020 at 20:02
  • @AntonTretyakov: don't shame yourself, the convention is ill-conceived and everybody makes mistakes. Learning from one's errors is a powerful way to improve. Share your learnings and help others improve too.
    – chqrlie
    Aug 13, 2020 at 20:05
  • 1
    @AntonTretyakov: Unlike python where integer arithmetic is performed on bignums, C does not do that: strt + end is performed on the larger of the types of strt and end, with some potentially counter-intuitive rules if the types have different signedness. in your case, both are int so the computation is performed in the int type and the behavior is undefined in case of overflow. The type of mid is irrelevant. The result will just be converted to the type of mid at assignment time.
    – chqrlie
    Aug 13, 2020 at 20:47
  • 1
    @chqrlie Dear Sir, i came here for a concrete answer for a concrete problem, but got a whole lecture - you have my deepest gratitude! Aug 13, 2020 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.