我正在尝试用 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)
最佳答案
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 时，它会很有帮助。
关于c - 合并排序算法中的运行时错误，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9490814/