ошибка времени выполнения в алгоритме сортировки слиянием

Question

Я пытаюсь написать алгоритм сортировки слиянием в C. Он компилирует и отлично работает для небольшого массива, но при попытке запустить его для большего размера я получаю сообщение об ошибке «glibc detected» n = 100). Я сделал некоторую отладку и обнаружил, что «обнаружение glibc» произошло сразу после функции free(). Я понятия не имею, как это исправить, я немного читал, и, похоже, это вызвано освобождением нераспределенной памяти, но я не понимаю, как это может произойти. Любые советы приветствуются. Вот мой код и сообщения об ошибках:

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

int mergeSort(int *arr, int size); 
int merge(int *arr, int arr1Start, int arrLen, int arr2End); 
void print_arr(int *arr, int size); 

int main(void) 
{ 
    int *arr; 
    int arrStart, arrEnd, size, i; 

    arrStart = 0; 
    size = 1000; 
    arrEnd = arrStart + size; 
    arr = (int*)malloc(size*sizeof(int)); 

    if (arr == NULL) 
    { 
     printf("failed to allocate memory for arr\n"); 
     return EXIT_FAILURE; 
    } 
    else 
    { 
     for (i=0; i<size; i++) 
     { 
      *(arr+i) = (int)(rand() % 99); 
     } 

     printf("unsorted array:\n"); 
     print_arr(arr, size); 

     if (mergeSort(arr, size) == EXIT_FAILURE) 
      return EXIT_FAILURE; 

     printf("sorted array:\n"); 
     print_arr(arr, size); 
     free(arr); 
    } 
    return EXIT_SUCCESS; 
} 

int mergeSort(int *arr, int size) 
{ 
    int i, j, arr2End; 

    for (i = 1; i < size; i *= 2) 
    { 
     for (j = 0; j < size-i; j += 2*i) 
     { 
      if (2*i < size - j) 
       arr2End = j + 2*i; 
      else 
       arr2End = j + size - j; 

      printf("arr1Start: %d, arrLen: %d, arr2End: %d\n", j, i, arr2End); 
      if (merge(arr, j, i, arr2End) == EXIT_FAILURE) 
       return EXIT_FAILURE ; 

     } 
    }   
    return EXIT_SUCCESS; 
} 

int merge(int *arr, int arr1Start, int arrLen, int arr2End) 
{ 
    int i, j, k; 
    int *tmp; 
    i = 0; 
    j = arrLen; 
    k = 0; 
    printf("trying to allocate array size %d\n", arrLen*2+1); 
    tmp = (int*)malloc((arrLen*2+1)*sizeof(int)); 
    if (tmp == NULL) 
    { 
     printf("failed to allocate memory for tmp:\n" 
       "arr2End: %d, arr1Start: %d\n", arr2End, arr1Start); 
     return EXIT_FAILURE; 
    } 
    else 
    { 
     while ((arr1Start+i < arr1Start+arrLen) && (arr1Start+j < arr2End)) 
     { 
      /*printf("in comparison loop\n");*/ 
      if (arr[arr1Start+i] < arr[arr1Start+j]) 
       tmp[k++] = arr[arr1Start + i++]; 
      else 
       tmp[k++] = arr[arr1Start + j++]; 
     } 
     while (i<arrLen) 
      tmp[k++] = arr[arr1Start + i++]; 
     while (j<arr2End) 
      tmp[k++] = arr[arr1Start + j++]; 

     /* debugging code 
     printf("***arr:"); 
     print_arr(arr, 7); 
     printf("***tmp:"); 
     print_arr(tmp, 7);*/ 

     memcpy(arr+arr1Start, tmp, (arr2End)*sizeof(int)); 

     /* more debugging code 
     printf("***arr2:"); 
     print_arr(arr, 7);*/ 

     printf("trying to free\n"); 
     free(tmp); 
     printf("freed\n"); 
    } 
    return EXIT_SUCCESS; 

} 

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

*** glibc detected *** /home/kc1g08/cw/a.out: free(): invalid next size (fast): 0x000000000d47afc0 *** 
======= Backtrace: ========= 
/lib64/libc.so.6[0x3de5271634] 
/lib64/libc.so.6(cfree+0x8c)[0x3de5274c5c] 
/home/kc1g08/cw/a.out[0x40098d] 
/home/kc1g08/cw/a.out[0x400780] 
/home/kc1g08/cw/a.out[0x4006c9] 
/lib64/libc.so.6(__libc_start_main+0xf4)[0x3de521d8b4] 
/home/kc1g08/cw/a.out[0x400549] 
======= Memory map: ======== 
00400000-00401000 r-xp 00000000 fd:02 2685870769       /home/kc1g08/cw/a.out 
00600000-00601000 rw-p 00000000 fd:02 2685870769       /home/kc1g08/cw/a.out 
0d47a000-0d49b000 rw-p 0d47a000 00:00 0         [heap] 
3de4e00000-3de4e1a000 r-xp 00000000 08:05 65837       /lib64/ld-2.5.so 
3de501a000-3de501b000 r--p 0001a000 08:05 65837       /lib64/ld-2.5.so 
3de501b000-3de501c000 rw-p 0001b000 08:05 65837       /lib64/ld-2.5.so 
3de5200000-3de534a000 r-xp 00000000 08:05 65838       /lib64/libc-2.5.so 
3de534a000-3de5549000 ---p 0014a000 08:05 65838       /lib64/libc-2.5.so 
3de5549000-3de554d000 r--p 00149000 08:05 65838       /lib64/libc-2.5.so 
3de554d000-3de554e000 rw-p 0014d000 08:05 65838       /lib64/libc-2.5.so 
3de554e000-3de5553000 rw-p 3de554e000 00:00 0 
3dea600000-3dea60d000 r-xp 00000000 08:05 65803       /lib64/libgcc_s-4.1.2-20080102.so.1 
3dea60d000-3dea80d000 ---p 0000d000 08:05 65803       /lib64/libgcc_s-4.1.2-20080102.so.1 
3dea80d000-3dea80e000 rw-p 0000d000 08:05 65803       /lib64/libgcc_s-4.1.2-20080102.so.1 
2b2f28f47000-2b2f28f49000 rw-p 2b2f28f47000 00:00 0 
2b2f28f69000-2b2f28f6b000 rw-p 2b2f28f69000 00:00 0 
2b2f2c000000-2b2f2c021000 rw-p 2b2f2c000000 00:00 0 
2b2f2c021000-2b2f30000000 ---p 2b2f2c021000 00:00 0 
7fffed853000-7fffed868000 rw-p 7ffffffea000 00:00 0      [stack] 
ffffffffff600000-ffffffffffe00000 ---p 00000000 00:00 0     [vdso] 

обновление: Я вынул бросание на таНос и побежал Valgrind и получил следующее. Но мне трудно понять это.

trying to free 
freed 
==27590== Invalid write of size 4 
==27590== at 0x4008DF: merge (mymergesort2.c:99) 
==27590== by 0x400738: mergeSort (mymergesort2.c:63) 
==27590== by 0x4006B2: main (mymergesort2.c:39) 
==27590== Address 0x4C2D04C is 0 bytes after a block of size 12 alloc'd 
==27590== at 0x4A05809: malloc (vg_replace_malloc.c:149) 
==27590== by 0x4007B1: merge (mymergesort2.c:79) 
==27590== by 0x400738: mergeSort (mymergesort2.c:63) 
==27590== by 0x4006B2: main (mymergesort2.c:39) 
==27590== 
==27590== Invalid read of size 1 
==27590== at 0x400916: merge (mymergesort2.c:107) 
==27590== by 0x400738: mergeSort (mymergesort2.c:63) 
==27590== by 0x4006B2: main (mymergesort2.c:39) 
==27590== Address 0x4C2D04C is 0 bytes after a block of size 12 alloc'd 
==27590== at 0x4A05809: malloc (vg_replace_malloc.c:149) 
==27590== by 0x4007B1: merge (mymergesort2.c:79) 
==27590== by 0x400738: mergeSort (mymergesort2.c:63) 
==27590== by 0x4006B2: main (mymergesort2.c:39) 
trying to free 
freed 
trying to free 
freed 
trying to free 
freed 
trying to free 
freed 
trying to free 
freed 
--27590-- VALGRIND INTERNAL ERROR: Valgrind received a signal 11 (SIGSEGV) - exiting 
--27590-- si_code=1; Faulting address: 0x804C2D1C2; sp: 0x4027A2D70 

valgrind: the 'impossible' happened: 
    Killed by fatal signal 
==27590== at 0x3802088D: vgPlain_arena_malloc (m_mallocfree.c:190) 
==27590== by 0x38035516: vgPlain_cli_malloc (replacemalloc_core.c:101) 
==27590== by 0x380022F5: vgMemCheck_malloc (mc_malloc_wrappers.c:182) 
==27590== by 0x38035BA7: do_client_request (scheduler.c:1158) 
==27590== by 0x380372B1: vgPlain_scheduler (scheduler.c:869) 
==27590== by 0x38051B59: run_a_thread_NORETURN (syswrap-linux.c:87) 

sched status: 
    running_tid=1 

Thread 1: status = VgTs_Runnable 
==27590== at 0x4A05809: malloc (vg_replace_malloc.c:149) 
==27590== by 0x4007B1: merge (mymergesort2.c:79) 
==27590== by 0x400738: mergeSort (mymergesort2.c:63) 
==27590== by 0x4006B2: main (mymergesort2.c:39) 

Answer 1

Valgrind указывает на ошибку. Вот как интерпретировать то, что он говорит:

==27590== Invalid write of size 4 

Ваша программа попыталась записать четыре байта памяти с недопустимым адресом.

==27590== at 0x4008DF: merge (mymergesort2.c:99) 
==27590== by 0x400738: mergeSort (mymergesort2.c:63) 
==27590== by 0x4006B2: main (mymergesort2.c:39) 

Это трассировка стека. Неверная запись произошла на линии 99 mymergesort.c, которая находится в функции merge. Ваш пример программы не имеют одни и те же номера строк, но я получаю ошибку на этой линии:

 tmp[k++] = arr[arr1Start + j++]; 

Это не сразу видно, что случилось там, так что двигаться дальше:

==27590== Address 0x4C2D04C is 0 bytes after a block of size 12 alloc'd 

«Адрес 0x4C2D04C "- неверный адрес, который программа пыталась написать. «0 байт после блока размера 12 alloc'd» означает, что плохая запись была только за окончанием выделения кучи malloc из 12 байтов. Это почти наверняка память, на которую указывает tmp.

Так что ваша настоящая ошибка не в том, что вы звоните free по неправильной вещи. Это то, что вы написали до конца tmp. Выясните, почему это происходит.

P.S. Вы можете игнорировать бит ==NUMBER== - это всего лишь идентификатор процесса программы, который сделал неправильную запись. Это может быть полезно, когда вы используете valgrind для чего-то, что вызывает fork.