c - 合并排序算法中的运行时错误

Question

我正在尝试用 C 语言编写合并排序算法。它编译并适用于小型数组，但当我尝试为更大的 (n=100) 数组运行它时，出现“glibc detected”错误。我做了一些调试，发现“glibc detected”发生在 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]

更新:我取出了 malloc 上的类型转换并运行了 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)

这是堆栈跟踪。无效写入发生在 mymergesort.c 的第 99 行，它位于函数 merge 中。您的示例程序没有相同的行号，但我在这一行收到错误:

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

目前还不是很明显那里出了什么问题，所以继续:

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

“地址 0x4C2D04C”是程序试图写入的无效地址。 “分配大小为 12 的 block 后有 0 个字节”意味着错误的写入刚好超过 12 字节的 malloc 堆分配的末尾。这几乎可以肯定是 tmp 指向的内存。

所以你的实际错误不是你在错误的事情上调用了 free。是你写过了tmp的末尾。弄清楚为什么会这样。

附言您可以忽略 ==NUMBER== 位——它只是进行无效写入的程序的进程 ID。当您在调用 fork 的东西上使用 valgrind 时，它会很有帮助。