I am trying to write a program in C that performs the merge sort algorithm on an array of integers. The code appears to run correctly and produces the right output, but when I run valgrind, I am informed of memory leak errors.
Here is my code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int *merge(int len_1, int len_2, int *arr1, int *arr2);
int *merge_sort(int len, int *arr);
int main(void){
int arr[] = {10, 3, 7, 5, 11, 16, 23, 14};
int len = sizeof(arr)/sizeof(arr[0]);
int *result = merge_sort(len, arr);
for (int i = 0; i < len; i++){
printf("%i\n", result[i]);
}
free(result);
return 0;
}
int *merge(int len_1, int len_2, int *arr1, int *arr2){
//Allocating memory for the output array
int *result = (int *)malloc(sizeof(int) * (len_1 + len_2));
//Initialising a pointer for both arrays
int p1 = 0;
int p2 = 0;
//Sorting the values
for (int i = 0 ; i < len_1 + len_2; i++){
if ((p1 < len_1) && (p2 >= len_2 || arr1[p1] <= arr2[p2])){
result[i] = arr1[p1];
p1++;
}
else{
result[i] = arr2[p2];
p2++;
}
}
return result;
}
int *merge_sort(int len, int *arr){
//An array with one element is already sorted
if (len == 1){
return arr;
}
//Compute midpoint and allocate memory
int midpoint = floor((float)len/2);
int *left = (int *)malloc(midpoint * sizeof(int));
int *right = (int *)malloc((len - midpoint) * sizeof(int));
//Assign the correct values to the left and right subarrays
for (int i = 0; i < midpoint; i++){
left[i] = arr[i];
}
for (int i = 0; i < len - midpoint; i++){
right[i] = arr[midpoint + i];
}
//Sort the left and right subarrays
int *left_sorted = merge_sort(midpoint, left);
int *right_sorted = merge_sort(len - midpoint, right);
//Merge the sorted subarrays
int *sorted_array = merge(midpoint, len - midpoint, left_sorted, right_sorted);
//Free memory
free(left);
free(right);
return sorted_array;
}
And here is the report from valgrind:
==39891== Memcheck, a memory error detector
==39891== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==39891== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==39891== Command: ./merge_sort
==39891==
3
5
7
10
11
14
16
23
==39891==
==39891== HEAP SUMMARY:
==39891== in use at exit: 64 bytes in 6 blocks
==39891== total heap usage: 21 allocs, 15 frees, 192 bytes allocated
==39891==
==39891== 8 bytes in 1 blocks are definitely lost in loss record 1 of 6
==39891== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==39891== by 0x109387: merge (merge_sort.c:24)
==39891== by 0x10932E: merge_sort (merge_sort.c:70)
==39891== by 0x109301: merge_sort (merge_sort.c:66)
==39891== by 0x109301: merge_sort (merge_sort.c:66)
==39891== by 0x1091BD: main (merge_sort.c:11)
==39891==
==39891== 8 bytes in 1 blocks are definitely lost in loss record 2 of 6
==39891== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==39891== by 0x109387: merge (merge_sort.c:24)
==39891== by 0x10932E: merge_sort (merge_sort.c:70)
==39891== by 0x109314: merge_sort (merge_sort.c:67)
==39891== by 0x109301: merge_sort (merge_sort.c:66)
==39891== by 0x1091BD: main (merge_sort.c:11)
==39891==
==39891== 8 bytes in 1 blocks are definitely lost in loss record 3 of 6
==39891== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==39891== by 0x109387: merge (merge_sort.c:24)
==39891== by 0x10932E: merge_sort (merge_sort.c:70)
==39891== by 0x109301: merge_sort (merge_sort.c:66)
==39891== by 0x109314: merge_sort (merge_sort.c:67)
==39891== by 0x1091BD: main (merge_sort.c:11)
==39891==
==39891== 8 bytes in 1 blocks are definitely lost in loss record 4 of 6
==39891== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==39891== by 0x109387: merge (merge_sort.c:24)
==39891== by 0x10932E: merge_sort (merge_sort.c:70)
==39891== by 0x109314: merge_sort (merge_sort.c:67)
==39891== by 0x109314: merge_sort (merge_sort.c:67)
==39891== by 0x1091BD: main (merge_sort.c:11)
==39891==
==39891== 16 bytes in 1 blocks are definitely lost in loss record 5 of 6
==39891== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==39891== by 0x109387: merge (merge_sort.c:24)
==39891== by 0x10932E: merge_sort (merge_sort.c:70)
==39891== by 0x109301: merge_sort (merge_sort.c:66)
==39891== by 0x1091BD: main (merge_sort.c:11)
==39891==
==39891== 16 bytes in 1 blocks are definitely lost in loss record 6 of 6
==39891== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==39891== by 0x109387: merge (merge_sort.c:24)
==39891== by 0x10932E: merge_sort (merge_sort.c:70)
==39891== by 0x109314: merge_sort (merge_sort.c:67)
==39891== by 0x1091BD: main (merge_sort.c:11)
==39891==
==39891== LEAK SUMMARY:
==39891== definitely lost: 64 bytes in 6 blocks
==39891== indirectly lost: 0 bytes in 0 blocks
==39891== possibly lost: 0 bytes in 0 blocks
==39891== still reachable: 0 bytes in 0 blocks
==39891== suppressed: 0 bytes in 0 blocks
==39891==
==39891== For lists of detected and suppressed errors, rerun with: -s
==39891== ERROR SUMMARY: 6 errors from 6 contexts (suppressed: 0 from 0)
I think I have not freed some memory somewhere after using malloc, but I’m not sure where I should be freeing memory from. I free the memory allocated to result, but I don’t see what else I could free?
Any insights would be greatly appreciated.
EDIT
I made the following adjustment to the merge_sort function:
//Free memory
free(left);
free(right);
free(left_sorted);
free(right_sorted);
The valgrind report is now as follows:
==55558== Memcheck, a memory error detector
==55558== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==55558== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==55558== Command: ./merge_sort
==55558==
==55558== Invalid free() / delete / delete[] / realloc()
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x10934D: merge_sort (merge_sort.c:75)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Address 0x4bb5180 is 0 bytes inside a block of size 4 free'd
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x10933B: merge_sort (merge_sort.c:73)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Block was alloc'd at
==55558== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109263: merge_sort (merge_sort.c:54)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558==
==55558== Invalid free() / delete / delete[] / realloc()
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109356: merge_sort (merge_sort.c:76)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Address 0x4bb51d0 is 0 bytes inside a block of size 4 free'd
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109344: merge_sort (merge_sort.c:74)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Block was alloc'd at
==55558== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109279: merge_sort (merge_sort.c:55)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558==
==55558== Invalid free() / delete / delete[] / realloc()
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x10934D: merge_sort (merge_sort.c:75)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Address 0x4bb5270 is 0 bytes inside a block of size 4 free'd
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x10933B: merge_sort (merge_sort.c:73)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Block was alloc'd at
==55558== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109263: merge_sort (merge_sort.c:54)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558==
==55558== Invalid free() / delete / delete[] / realloc()
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109356: merge_sort (merge_sort.c:76)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Address 0x4bb52c0 is 0 bytes inside a block of size 4 free'd
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109344: merge_sort (merge_sort.c:74)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Block was alloc'd at
==55558== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109279: merge_sort (merge_sort.c:55)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558==
==55558== Invalid free() / delete / delete[] / realloc()
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x10934D: merge_sort (merge_sort.c:75)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Address 0x4bb5450 is 0 bytes inside a block of size 4 free'd
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x10933B: merge_sort (merge_sort.c:73)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Block was alloc'd at
==55558== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109263: merge_sort (merge_sort.c:54)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558==
==55558== Invalid free() / delete / delete[] / realloc()
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109356: merge_sort (merge_sort.c:76)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Address 0x4bb54a0 is 0 bytes inside a block of size 4 free'd
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109344: merge_sort (merge_sort.c:74)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Block was alloc'd at
==55558== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109279: merge_sort (merge_sort.c:55)
==55558== by 0x109301: merge_sort (merge_sort.c:66)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558==
==55558== Invalid free() / delete / delete[] / realloc()
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x10934D: merge_sort (merge_sort.c:75)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Address 0x4bb5540 is 0 bytes inside a block of size 4 free'd
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x10933B: merge_sort (merge_sort.c:73)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Block was alloc'd at
==55558== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109263: merge_sort (merge_sort.c:54)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558==
==55558== Invalid free() / delete / delete[] / realloc()
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109356: merge_sort (merge_sort.c:76)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Address 0x4bb5590 is 0 bytes inside a block of size 4 free'd
==55558== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109344: merge_sort (merge_sort.c:74)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558== Block was alloc'd at
==55558== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==55558== by 0x109279: merge_sort (merge_sort.c:55)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x109314: merge_sort (merge_sort.c:67)
==55558== by 0x1091BD: main (merge_sort.c:11)
==55558==
3
5
7
10
11
14
16
23
==55558==
==55558== HEAP SUMMARY:
==55558== in use at exit: 0 bytes in 0 blocks
==55558== total heap usage: 21 allocs, 29 frees, 192 bytes allocated
==55558==
==55558== All heap blocks were freed -- no leaks are possible
==55558==
==55558== For lists of detected and suppressed errors, rerun with: -s
==55558== ERROR SUMMARY: 8 errors from 8 contexts (suppressed: 0 from 0)
The code also no longer runs, displaying the following error in Bash:
free(): double free detected in tcache 2
Aborted (core dumped)
It appears that adding those free() lines removed the memory leak error but now something else seems to have gone horribly wrong and I’m not sure why.
>Solution :
The minimal fix is to free left_sorted and right_sorted in merge_sort() if the recursive call allocated a new array (i.e. len > 1). Ideally you want malloc() and free() happens in the same function. It makes it easier to reason about.
While I appreciate the functional style (consider const for both arr1 and arr2 in current design), could caller pass a suitable array into merge_sort() so you only need 1 malloc() in main() instead of 22?
(Not fixed) Always check the return value of malloc().
int *merge_sort(int len, int *arr) {
if (len == 1)
return arr;
int midpoint = len / 2;
int *left = malloc(sizeof *left * midpoint);
for (int i = 0; i < midpoint; i++)
left[i] = arr[i];
int *left_sorted = merge_sort(midpoint, left);
free(left);
int *right = malloc(sizeof *right * (len - midpoint));
for (int i = 0; i < len - midpoint; i++)
right[i] = arr[midpoint + i];
int *right_sorted = merge_sort(len - midpoint, right);
free(right);
int *sorted_array = merge(midpoint, len - midpoint, left_sorted, right_sorted);
if(midpoint > 1)
free(left_sorted);
if(len - midpoint > 1)
free(right_sorted);
return sorted_array;
}
and result run via valgrind:
==2997412== HEAP SUMMARY:
==2997412== in use at exit: 0 bytes in 0 blocks
==2997412== total heap usage: 22 allocs, 22 frees, 1,216 bytes allocated