c - valgrind 测试内存管理出错？

Question

我编写了一个C程序来比较插入排序和计数排序的运行时间，但它无法通过valgrind测试，因为该程序将从未初始化的内存中读取。这是我的代码，可能是错误的，我想知道为什么会出现这个问题:

void count_sort_write_output_array(int output_array[], int len, int count_array[], int* befehle) {
    int k=0;
    //use count array to output result
    for (int j=0;j<=MAX_VALUE;j++) {
        //add befehle
        //(j++)
        (*befehle)++;
        for (int i=0; i<count_array[j]; i++) {
            output_array[k] = j;
            k++;
            //add befehle
            //(i++, output_array[k] = j, k++)
            (*befehle)+=3;
        }
    }
}

void count_sort(int array[], int len, int* befehle) {
    int* count_array = malloc(sizeof(int) * MAX_VALUE);

    //fill count_array with 0
    for(int i=0;i<MAX_VALUE;i++){
        count_array[i] = 0;
    }

    count_sort_calculate_counts(array, len, count_array, befehle);

    //use output array to save result
    count_sort_write_output_array(array, len, count_array, befehle);

    free(count_array);

}

这是 valgrind 的结果:

==6694== Memcheck, a memory error detector
==6694== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==6694== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==6694== Command: ./aaaad
==6694== 
==6694== Invalid read of size 4
==6694==    at 0x4009ED: count_sort_write_output_array (in /afs/tu-berlin.de/home/r/ryoine/irb-ubuntu/introprog-wise1718/Tutorien/t24/Studierende/ryoine/Abgaben/Blatt03/aaaad)
==6694==    by 0x400A8D: count_sort (in /afs/tu-berlin.de/home/r/ryoine/irb-ubuntu/introprog-wise1718/Tutorien/t24/Studierende/ryoine/Abgaben/Blatt03/aaaad)
==6694==    by 0x400FD5: main (in /afs/tu-berlin.de/home/r/ryoine/irb-ubuntu/introprog-wise1718/Tutorien/t24/Studierende/ryoine/Abgaben/Blatt03/aaaad)
==6694==  Address 0x6916d40 is 0 bytes after a block of size 20,000,000 alloc'd
==6694==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6694==    by 0x400A2A: count_sort (in /afs/tu-berlin.de/home/r/ryoine/irb-ubuntu/introprog-wise1718/Tutorien/t24/Studierende/ryoine/Abgaben/Blatt03/aaaad)
==6694==    by 0x400FD5: main (in /afs/tu-berlin.de/home/r/ryoine/irb-ubuntu/introprog-wise1718/Tutorien/t24/Studierende/ryoine/Abgaben/Blatt03/aaaad)
==6694== 
Parameter MAX_VALUE hat den Wert 5000000
                                Countsort                              Insertionsort 
       n                  Befehle         Laufzeit                Befehle         Laufzeit 
   10000                  5050001         425.5080               50215642        1929.5740       
   20000                  5100001         423.1040              200387176        7655.5280       
   30000                  5150001         427.7080              453403054       16763.7200       
   40000                  5200001         363.3830              797737482       28034.7020       
   50000                  5250001         392.9350             1245274822       44438.0240       
==6694== 
==6694== HEAP SUMMARY:
==6694==     in use at exit: 0 bytes in 0 blocks
==6694==   total heap usage: 26 allocs, 26 frees, 101,224,264 bytes allocated
==6694== 
==6694== All heap blocks were freed -- no leaks are possible
==6694== 
==6694== For counts of detected and suppressed errors, rerun with: -v
==6694== ERROR SUMMARY: 5 errors from 1 contexts (suppressed: 0 from 0)

Answer 1

这是你的问题:

for (int j=0;j<=MAX_VALUE;j++) {

您为 MAX_VALUE int 数组分配空间。因此该数组的索引范围为 0 到 MAX_VALUE - 1。然而，您的循环允许 j 的范围最大为 MAX_VALUE，因此当发生这种情况时，count_array[j] 正在读取超出数组末尾的一个元素.

修复循环条件，使其不包含 MAX_VALUE:

for (int j=0;j<MAX_VALUE;j++) {