Ce forum est en partie financé par l’affichage de publicités. Merci de désactiver votre bloqueur de publicités pour nous permettre de continuer à fournir ce service.

plantage d'une appli en C

Discussion dans 'Développement Mac' créé par -anonyme-, 13 Juillet 2003.

  1. -anonyme-

    -anonyme- Légende

    Inscrit:
    26 Février 2001
    Messages:
    66 286
    J'aime reçus:
    2 668
    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
     
  2. Didier Guillion

    Didier Guillion Membre d’élite
    Club MacG

    Inscrit:
    20 Juillet 2001
    Messages:
    3 244
    J'aime reçus:
    164
    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
     
  3. jemeor

    jemeor Membre junior

    Inscrit:
    16 Septembre 2002
    Messages:
    52
    J'aime reçus:
    0
    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.

    [​IMG]
     
  4. Didier Guillion

    Didier Guillion Membre d’élite
    Club MacG

    Inscrit:
    20 Juillet 2001
    Messages:
    3 244
    J'aime reçus:
    164
    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
     
  5. arnolix

    arnolix Membre junior

    Inscrit:
    15 Juillet 2003
    Messages:
    80
    J'aime reçus:
    3
    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.
     
  6. Didier Guillion

    Didier Guillion Membre d’élite
    Club MacG

    Inscrit:
    20 Juillet 2001
    Messages:
    3 244
    J'aime reçus:
    164
    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
     
  7. jemeor

    jemeor Membre junior

    Inscrit:
    16 Septembre 2002
    Messages:
    52
    J'aime reçus:
    0
    Si tu as besoin d'un maximum de rapidité, les questions d'optimisations deviennent très interessantes [​IMG]

    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 [​IMG]



     
  8. molgow

    molgow Vétéran
    Club MacG

    Inscrit:
    4 Janvier 2002
    Messages:
    5 493
    J'aime reçus:
    612
    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 ?
     
  9. jemeor

    jemeor Membre junior

    Inscrit:
    16 Septembre 2002
    Messages:
    52
    J'aime reçus:
    0
    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é [​IMG]
     
  10. arnolix

    arnolix Membre junior

    Inscrit:
    15 Juillet 2003
    Messages:
    80
    J'aime reçus:
    3
    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.
     
Chargement...