Malloc se bloque dans la fonction récursive

Question

Je suis en train de coder une implémentation de la transformation Burrows-Wheeler qui nécessite de trier un (grand) tableau. Puisque je veux paralléliser des parties du code d'une fonction de tri récursive, j'ai décidé d'allouer certaines des variables locales dans le tas (en utilisant malloc()) pour éviter les débordements de pile ou - au moins - faire grimper le programme gracieusement. Cela a soulevé toute une série de problèmes. J'ai réduit le code à la partie essentielle (c'est-à-dire, ce qui cause les problèmes).

Le code suivant est compilé sans erreur. Le programme résultant fonctionne correctement lorsqu'il est compilé avec icc, mais il se bloque (aléatoirement) lorsqu'il est compilé avec gcc ou 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); 
} 

Même lorsque l'entrée est un fichier texte très petit (environ 50 octets), le programme est très instable avec les deux derniers compilateurs. Cela fonctionne avec une probabilité de ~ 50%. Dans les autres cas, il se bloque dans la 2ème ou 3ème itération de radixsort lors de l'appel malloc(). Il se bloque toujours lorsque le fichier d'entrée est plus gros (environ 1 Mio). Également dans la 2ème ou 3ème itération ...

Augmenter manuellement le tas ne fait rien de bon. De toute façon, ça ne devrait pas. Si malloc() ne peut pas allouer la mémoire, il doit renvoyer un pointeur NULL (et ne pas tomber en panne).

Le retour du tas vers la pile fait fonctionner le programme avec l'un ou l'autre compilateur (tant que le fichier d'entrée est suffisamment petit).

Alors, qu'est-ce qui me manque/mal?

Answer 1

if((occurrences = malloc(1024)) == 0) 

make that: 

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

Mais il y a plus de problèmes ...

MISE A JOUR (1024 = 4 * 256 semble simplement stylistique ...)

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

L'indice [i + 1] traiterai le tableau au-delà de sa taille;