Malloc падает в рекурсивной функции - PullRequest
Новая
       15

Malloc падает в рекурсивной функции

0 голосов
/ 24 сентября 2011

В настоящее время я пишу реализацию преобразования Берроуза-Уилера, которое требует сортировки (большого) массива.Поскольку я хочу распараллелить части кода функции рекурсивной сортировки, я решил выделить некоторые локальные переменные в куче (используя malloc()), чтобы предотвратить переполнение стека или - по крайней мере - заставить программу изящно умереть.Это подняло целую кучу новых проблем.Я сократил код до основной части (то есть, что вызывает проблемы).

Следующий код компилируется без ошибок.Получающаяся в результате программа работает нормально при компиляции с помощью icc, но происходит сбой (случайным образом) при компиляции с помощью gcc или tcc. 

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

unsigned char *block;
int *indexes, *indexes_copy;

void radixsort(int from, int to, int step)
{
    int *occurrences, *first_index_of, i;
    if((occurrences = malloc(1024)) == 0)
        exit(1);
    if((first_index_of = malloc(1024)) == 0)
        exit(1);
    memset(occurrences, 0, 1024);
    for(i = from; i < to; i++)
        occurrences[block[indexes[i] + step]]++;
    first_index_of[0] = from;
    for(i = 0; i < 256; i++)
        first_index_of[i + 1] = first_index_of[i] + occurrences[i];
    memset(occurrences, 0, 1024);
    memcpy(&indexes_copy[from], &indexes[from], 4 * (to - from));
    for(i = from; i < to; i++)
        indexes[first_index_of[block[indexes_copy[i] + step]] + occurrences[block[indexes_copy[i] + step]]++] = indexes_copy[i];
    for(i = 0; i < 256; i++)
    if(occurrences[i] > 1)
        radixsort(first_index_of[i], first_index_of[i] + occurrences[i], step + 1);
    free(occurrences);
    free(first_index_of);
}

int main(int argument_count, char *arguments[])
{
    int block_length, i;
    FILE *input_file = fopen(arguments[1], "rb");
    fseek(input_file, 0, SEEK_END);
    block_length = ftell(input_file);
    rewind(input_file);
    block = malloc(block_length);
    indexes = malloc(4 * block_length);
    indexes_copy = malloc(4 * block_length);
    fread(block, 1, block_length, input_file);
    for(i = 0; i < block_length; i++)
        indexes[i] = i;
    radixsort(0, block_length, 0);
    exit(0);
}

Даже если ввод представляет собой очень маленький текстовый файл (около 50 байт), программа очень нестабильно с последними двумя компиляторами.Это работает с вероятностью ~ 50%.В других случаях происходит сбой во 2-й и 3-й итерации radixsort при вызове malloc().Это всегда падает, когда размер входного файла больше (около 1 МБ).Также во 2-й или 3-й итерации ...

Ручное увеличение кучи не приносит пользы.В любом случае, это не должно быть.Если malloc() не может выделить память, он должен вернуть указатель NULL (а не сбой).

Переключение обратно из кучи в стек заставляет программу работать с любым компилятором (при условии, что вводфайл достаточно маленький).

Итак, что я пропускаю / делаю неправильно?

1 Ответ

1 голос
/ 24 сентября 2011 
if((occurrences = malloc(1024)) == 0)

make that:

if((occurrences = malloc(1024 * sizeof *occurences)) == 0)

Но есть и другие проблемы ...

ОБНОВЛЕНИЕ (1024 = 4 * 256 кажется просто стилистическим ...) 

for(i = 0; i < 256; i++)
    first_index_of[i + 1] = first_index_of[i] + occurrences[i];

[i + 1]index будет обращаться к массиву за пределами его размера;

...