plantage d'une appli en C

[Membre supprimé 2]

bonjour, je programme une petite appli en C de type Standard Tool sous ProjectBuilder (pas d'interface GUI). La fonction principale de ce programme est récursive.
Lors du débogage j'ai le message suivant suivi d'un plantage :
"warning: ppc_frame_chain_valid: stack pointer from 0xbffff670 to 0x1bbc grows upward; assuming invalid"
Qu'est ce que : "ppc_frame_chain_valid" ?
Je comprends vaguement que le pointeur de pile croît vers le haut ("grows upward" ?) et qu'il aime pas trop ("assuming invalid"). Quelqu'un peut-il m'expliquer ces problèmes de pile ?
Merci

 

[Didier Guillion]

Bonjour,

ppc_frame_chain_valid est une fonction qui vérifie la logique de la pile (il me semble)?
Tu dois avoir une saturation ou un débordement dans ta recursivité.

Une erreur classique est de déclarer des tableaux en variable locale ce qui sature rapidement la pile.

Par exemple :

void MaFonction(void)
{
char machaine[255];

// Mon code
}

n'est pas bon.

Ecrire plutot :
void MaFonction(void)
{
char * machaine;

machaine=malloc(255);
if(machaine!=NULL)
{
// Mon code
free(machaine);
}
}

Ce qui utilise la memoire de la heap plutot que la mémoire de la pile, plus limitée.

Cordialement

 

[jemeor]

Salut,
A chaque fois que la fonction récursive s'appelle, la taille utilisée de la pile augmente, et s'il y a trop de recursions, la pile sature (déborde). Si ton algo ne plante qu'au dela d'un certain nombre de recursions, c'est certainement un débordement de pile.

Tu as plusieurs solutions:
Economiser un maximum d'allocations sur la pile, comme le décrit Didier: les tableaux, structures, objets, variables que tu peux éviter de declarer dans la fonction. Mais à moins de connaitre présisement les limites de ton algo, ca ne t'empechera pas un jour ou l'autre de remplir la pile. Par contre, j'eviterai de faire de l'allocation dynamique de mémoire dans un fonction récursive, ca doit être terriblement lent au final.

Augmenter la taille de la pile, c'est 512 Ko par defaut. Mais ca ne te donnera pas plus de garanties que la solution précédente.

Economiser le nombre de récursions: soit mettre une limite, et informer l'utilisateur en affichant une alerte si ton algo n'est pas capable de traiter le problème (c'est toujours mieux que de planter). Soit, si possible, découper ton traitements en plusieurs phases, chaque phase ne depassant pas le nombre critique de recursions.

Le mieux, si tu peux, c'est de remplacer ton code par un algorithme qui n'utilise pas la récursion, il sont en principe beaucoup plus rapides, et ne maltraitent pas la pile.

 

[Didier Guillion]

Bonsoir,

Je suis d'accord avec ce que dit Jemeor.
Bien que l'on se rende compte, en fait, que les allocations dans une recursivité sont plutot rapide car elles se font statistiquement souvent à la même place du tas (heap).

Et puis, une récursivité, c'est si joli, ce serait dommage de s'en passer !

Pour limiter le nombre de niveaux, cela donne un truc du genre

#define MA_LIMITE 512
Boolean MaFonction(short level)
{
if(level>MA_LIMITE)
return(false);
// ton code qui cherche le resultat
if(resultatTrouve)
return(true);
// on continue la recherche un niveau en dessous
return(MaFonction(level+1));
}

main()
{
if(MaFonction(0)==false)
printf("Depassement de recursivite");
}

Cordialement

 

[arnolix]

Merci beaucoup pour vos conseils. C'est effectivement depuis que j'ai rajouté une déclaration locale d'un tableau que ce problème s'est déclaré. J'ai donc utilisé l'allocation dynamique selon le modèle de Didier et le problème est maintenant réglé (de ce côté la, néanmoins :-( ).
Cependant Jemeor tu évoques la possiblité de régler la taille de la pile (je suis surpris d'ailleurs que les 512ko ait été si vite bouffés) : comment fait-on ? Je ne peux pas en effet me passer de la récursion car dans ce cas le problème est ouvert (génération de carrés magiques).
Merci encore.

 

[Didier Guillion]

Bonsoir,

Voici un extait de la doc de gcc (man gcc dans le terminal)
-fstack-check
Generate code to verify that you do not go beyond the
boundary of the stack. You should specify this flag
if you are running in an environment with multiple
threads, but only rarely need to specify it in a sin-
gle-threaded environment since stack overflow is auto-
matically detected on nearly all systems if there is
only one stack.

Note that this switch does not actually cause checking
to be done; the operating system must do that. The
switch causes generation of code to ensure that the
operating system sees the stack being extended.

-fstack-limit-register=reg
-fstack-limit-symbol=sym
-fno-stack-limit
Generate code to ensure that the stack does not grow
beyond a certain value, either the value of a register
or the address of a symbol. If the stack would grow
beyond the value, a signal is raised. For most tar-
gets, the signal is raised before the stack overruns
the boundary, so it is possible to catch the signal
without taking special precautions.

For instance, if the stack starts at absolute address
0x80000000 and grows downwards, you can use the flags
-fstack-limit-symbol=__stack_limit and -Wl,--def-
sym,__stack_limit=0x7ffe0000 to enforce a stack limit
of 128KB. Note that this may only work with the GNU
linker.

Non testé.

Cordialement

 

[jemeor]

Si tu as besoin d'un maximum de rapidité, les questions d'optimisations deviennent très interessantes

A propos de l'allocation mémoire, effectivement, s'il n'y a pas accumulation (on libère la memoire avant la recursion), mais répétition, ca peut être rapide. A ce moment là, on doit pouvoir s'en sortir en allouant une fois pour toutes. Penser que ce qui se passe en memoire cache est très important pour la rapidité d'un algorithme.

Si au contraire, il y a accumulation de mémoire, et que tu as besoins d'un maximum de rapidité, tu peux allouer un gros bloc mémoire par avance, et y simuler le comportement d'une pile.

Les algo recursifs sont réputés pratiques, mais lents, car c'est une énorme succession d'appels de fonction, et que tu parcours une grande zone mémoire (toute ta pile, en l'occurence, quand tu plantais), toujours des histoires de mémoire cache.

A vrai dire, je n'ai jamais eu de soucis de pile avec OS-X. J'ai cru comprendre que la limite etait 512Ko par defaut, je ne sais absolument pas comment on le modifie

 

[molgow]

Le problème vient peut-être tout simplement du fait que la récursion ne s'arrête jamais. Il y a bien une condition d'arrêt qui peut devenir vraie ?

 

[jemeor]

Le problème vient peut-être tout simplement du fait que la récursion ne s'arrête jamais. Il y a bien une condition d'arrêt qui peut devenir vraie ?

Bein... quand le carré est résolu non ? Je ne peut pas trop te répondre, je ne sais pas du tout ce que fait ton algorithme. C'est toi qui l'a fait ou tu l'as trouvé quelque part ¿

Moi quand j'étais jeune, vin'diu, j'avais fais un algo de barbare pour faire des carrés magiques. Je remplissais le carré en mettant les nombres au hazard, puis à la fin je testais s'il etait magique. Sur un vieux 68030 a 16 Mhz, programmé en basic, il mettait quelque secondes pour en trouver un, mais je n'ai jamais essayé avec des carrés de plus de 5 cases de coté

 

[arnolix]

En fait l'appli engendre tous les carrés magiques d'ordre n donné. Cependant c'est un prog que j'ai déjà fait lorsque j'étais étudiant mais en Pascal. Il tourne sous OS9. Mais j'aimerais l'utiliser sous OSX (sans passer par classic) et je ne connais pas de compilateur Pascal sous OSX et qui soit gratuit (j'ai déjà casqué pour CodeWarrior sous OS9). C'est pour cela que je me suis lancé dans le C (et plus tard peut-être en Cocoa ?) et ai rencontré les soucis que j'ai déjà évoqués.
Pour ce qui est du pb de la terminaison de la récursion, il est résolu. Par contre pour l'optimisation je verrai plus tard.
Le réglage de la taille de la pile me semble assez fastidieux, peu orthodoxe voire risqué.
La solution de Didier est tout à fait satisfaisante puisque ça fonctionne dorénavant.
MàJ : viens de découvrir en recherchant sur le forum (chose que j'aurai du faire en premier, grrrr...) qu'un compilo en Pascal existe en free.