c-在mergesort中的堆外写入

Question

我一直在C中实现普通版本的合并排序。在排序部分(这是一个单独的函数(中，我通过malloc创建了一个临时数组，如下所示：

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

由于某种原因，我在比较后试图用元素填充临时数组时，在整个临时数组中得到了无效的读写操作。int tmp_arr[end - strt];运行良好。

为什么我要在堆外写作(如果我目前的理解不正确，会发生什么(？

以下是使用malloc的函数，从valgrind输出中提取，以及我在执行时遇到的确切错误。我没有忘记free的东西。

我对最初的数组进行了硬编码，因为我想写这些东西，然后再麻烦输入。

这个特殊的数组{ 8, 1, 10, 54, 2, 0, -3, 5, 70, 60, 11, 4 }具有最大长度，如果较长的程序因文章末尾描述的错误而崩溃，我可以让我的程序运行。Valgrind的输出原则上总是一样的，数组越长，我的读写错误就越多。

程序：

#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);
}

从valgrind输出中提取，上面的阵列硬编码：

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)

我在执行时犯的错误：

main:malloc.c:2401:sysmalloc:Assertion`(old_top==initial_top(av(&amp；old_size==0(||((无符号长((old_size(>=MINSIZE&amp；prev_ inus e(old_top(&amp；((无符号长(old_end&(页面大小-1(==0('失败。退出，中止

Answer 1

问题是要排序的切片的长度不是end - strt，而是end - strt + 1，因为您正在使用易于出错的约定来包括end元素。

分配应为int *tmp_arr = malloc(sizeof *tmp_arr * (end - strt + 1));

代码似乎可以使用本地声明的带有自动存储的数组，这完全是偶然的。当将数据存储到tmp_arr[end - strt]时，您仍然有未定义的行为，但碰巧它似乎没有任何不利的副作用，而当您对已分配的对象执行此操作时，您可能会损坏malloc()用于跟踪已分配块的内部数据，这些数据会被分配例程或valgrind执行的一致性检查检测到。

将索引包含到切片中的最后一个元素是非常容易出错的。我希望在任何具有基于0的数组索引的语言的编程类中不再教授这种无稽之谈。它需要在代码中进行许多令人困惑的+1/-1调整，而使用最后一个元素之后的元素索引可以实现更简单的代码。

这是一个修改版本：

#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);
}