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

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

1 голос
/ 29 февраля 2012

Я пытаюсь написать алгоритм сортировки слиянием на C. Он компилируется и отлично работает для небольшого массива, но я получаю ошибку "glibc обнаружено", когда пытаюсь запустить его для большего (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]

update: я вынул приведение к 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)

1 Ответ

2 голосов
/ 29 февраля 2012

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.

...