Taille de la pile Estimation

Question

Dans le logiciel embarqué multithread (écrit en C ou C ++), un fil doit être donné assez d'espace de pile afin de lui permettre d'achever ses opérations sans déborder. Un dimensionnement correct de la pile est critique dans certains environnements embarqués en temps réel, parce que (au moins dans certains systèmes, j'ai travaillé), le système d'exploitation ne détectera pas pour vous.

Habituellement, la taille de la pile pour un nouveau fil (autre que le fil principal) est désigné au moment où ce fil est créé (par exemple dans un argument pour pthread_create () ou analogue). Souvent, ces tailles de piles sont codées en dur à des valeurs qui sont connus pour être bon au moment où le code a été écrit ou testé.

Toutefois, l'évolution future du code souvent briser les hypothèses sur lesquelles les tailles de pile codées en dur étaient fondées, et un jour fatidique, votre fil entre dans l'une des branches les plus profondes de son graphe d'appel et déborde la pile - faire tomber l'ensemble du système ou en mode silencieux corrompre la mémoire.

J'ai personnellement vu ce problème dans le cas où le code exécuté dans le thread déclare instances de struct sur la pile. Lorsque la structure est augmentée pour contenir des données supplémentaires, la taille de la pile se gonfle en conséquence, ce qui permet potentiellement débordements de pile de se produire. J'imagine que cela pourrait être un énorme problème pour codebases établi où les effets de l'ajout de champs à une structure ne peut pas être connue immédiatement (trop de threads / fonctions pour trouver tous les endroits où que struct est utilisé).

Depuis la réponse habituelle aux questions « dimensionnement pile » est « ils ne sont pas portables », supposons que le compilateur, système d'exploitation, et le processeur sont toutes les quantités connues pour cette enquête. Supposons aussi récursion est pas utilisé, donc nous ne sommes pas face à la possibilité d'un scénario de « récursion infinie ».

Quels sont les moyens fiables pour estimer la taille de la pile nécessaire à un fil? Je préfère les méthodes qui sont hors ligne (analyse statique) et automatique, mais toutes les idées sont les bienvenus.

Answer 1

Runtime-évaluation

Une méthode en ligne est de peindre la pile avec une certaine valeur, comme 0xAAAA (ou 0xAA, quel que soit votre largeur). Ensuite, vous pouvez vérifier la taille de la pile a au maximum grandi dans le passé en vérifiant la quantité de la peinture reste intacte.

Jetez un oeil à ce lien pour une explication avec illustration.

L'avantage est qu'il est simple. Un inconvénient est que vous ne pouvez pas être certain que votre taille de la pile ne finira par dépasser le montant de la pile utilisée lors de vos tests.

Évaluation statique

Il y a des contrôles statiques et je pense qu'il existe même une version gcc piraté qui tente de le faire. La seule chose que je peux vous dire est que le contrôle statique est très difficile à faire dans le cas général.

Voir aussi cette question .

Answer 2

Vous pouvez utiliser un outil d'analyse statique comme StackAnalyzer , si votre cible correspond aux exigences.

Answer 3

Si vous voulez dépenser de l'argent importante, vous pouvez utiliser un outil d'analyse statique commerciale comme Klocwork. Bien que Klocwork est principalement destiné à détecter les défauts logiciels et les failles de sécurité. Cependant, il a aussi un outil appelé « kwstackoverflow » qui peut être utilisé pour détecter un dépassement de pile dans une tâche ou d'un fil. J'utilise pour le projet intégré que je travaille, et j'ai eu des résultats positifs. Je ne pense pas que tout outil comme celui-ci est parfait, mais je crois que ces outils commericial sont très bons. La plupart des outils que je suis venu à travers la lutte avec des pointeurs de fonction. Je sais aussi que de nombreux fournisseurs de compilateur comme Green Hills construire maintenant des fonctionnalités similaires à droite dans leurs compilateurs. Ceci est probablement la meilleure solution, car le compilateur a une connaissance intime de tous les détails nécessaires pour prendre des décisions précises sur la taille de la pile.

Si vous avez le temps, je suis sûr que vous pouvez utiliser un langage de script pour faire votre propre outil d'analyse de débordement de pile. Le script aurait besoin d'identifier le point d'entrée de la tâche ou fil, générer un arbre d'appel de fonction complète, puis de calculer la quantité d'espace de pile que chaque fonction utilise. Je pense qu'il ya probablement des outils gratuits disponibles qui peuvent générer un arbre d'appel de fonction complète ce qui devrait faciliter. Si vous connaissez les spécificités de votre plate-forme générant l'espace de pile chaque fonction utilise peut être très facile. Par exemple, la première instruction de montage d'une fonction PowerPC est souvent le mot de magasin avec instruction de mise à jour qui ajuste le pointeur de la pile par la quantité nécessaire pour la fonction. Vous pouvez prendre la taille en octets dès la première instruction qui permet de déterminer l'espace total de pile utilisé relativement facile.

Ces types d'analyse seront tous vous donner une approximation du pire des cas limite supérieure pour l'utilisation de la pile qui est exactement ce que vous voulez savoir. Bien sûr, les experts (comme ceux avec lesquels je travaille) pourraient se plaindre que vous allouer trop d'espace de pile, mais ils sont des dinosaures qui ne se soucient pas de bonne qualité logicielle:)

Une autre possibilité, même si elle ne calcule pas l'utilisation de la pile serait d'utiliser l'unité de gestion de la mémoire (MMU) de votre processeur (si elle en a un) pour détecter un débordement de pile. Je l'ai fait sur VxWorks 5.4 en utilisant un PowerPC. L'idée est simple, il suffit de mettre une page d'écriture de mémoire protégée au sommet de votre pile. Si vous débordez, un Execption processeur se produit et vous sera rapidement alerté au problème de débordement de pile. Bien sûr, il ne vous dit pas par combien vous avez besoin d'augmenter la taille de la pile, mais si votre bien avec les fichiers exception de débogage / noyau, vous pouvez au moins déterminer la séquence d'appel qui débordait la pile. Vous pouvez ensuite utiliser ces informations pour augmenter la taille de votre pile de façon appropriée.

-djhaus

Answer 4

Pas libre, mais Coverity fait l'analyse statique de la pile.

Answer 5

statique (hors ligne) vérification de la pile n'est pas aussi difficile que cela puisse paraître. Je l'ai mis en œuvre pour notre IDE intégré ( RapidiTTy ) - il travaille actuellement pour ARM7 (NXP LPC2xxx ), Cortex-M3 (STM32 et NXP LPC17xx), x86 et notre en interne MIPS ISA compatible FPGA core douce.

Pour l'essentiel, nous utilisons un Parse simple du code exécutable pour déterminer l'utilisation de la pile de chaque fonction. Le plus important allocation de pile est effectué au début de chaque fonction; juste être sûr de voir comment il modifie avec différents niveaux d'optimisation et, le cas échéant, les jeux d'instructions ARM / Thumb, etc. Rappelons également que les tâches ont généralement leurs propres piles et ISRs souvent (mais pas toujours) partagent une zone de pile séparée!

Une fois que vous avez l'utilisation de chaque fonction, il est assez facile de construire un appel arbre de l'analyse syntaxique et de calculer l'utilisation maximale pour chaque fonction. Notre IDE génère ordonnanceurs (RTOS minces efficaces) pour vous, donc nous savons exactement quelles fonctions sont désignées comme des « tâches » et qui sont ISRs, afin que nous puissions dire l'utilisation du pire cas pour chaque zone de la pile.

Bien sûr, ces chiffres sont presque toujours sur la réelle au maximum. Pensez à une fonction comme sprintf qui peut utiliser un beaucoup de l'espace de la pile, mais varie énormément selon la chaîne de format et les paramètres que vous fournissez. Pour ces situations, vous pouvez également utiliser l'analyse dynamique - remplir la pile avec une valeur connue dans votre démarrage, puis exécutez dans le débogueur pendant un certain temps, mettre en pause et de voir la quantité de chaque pile est toujours remplie de votre valeur (test de style high watermark) .

Aucune de ces approches est parfaite, mais la combinaison de deux vous donnera une assez bonne idée de ce qui va être comme l'utilisation du monde réel.

Answer 6

Comme indiqué dans la réponse à la cette question, une technique courante consiste à initialiser la pile avec une valeur connue et puis exécuter le code pendant un certain temps et de voir où le motif se bloque.

Answer 7

Ce n'est pas une méthode hors ligne, mais sur le projet que je travaille, nous avons une commande de débogage qui lit la marque de haute eau sur toutes les piles de tâches dans l'application. Cette affiche une table de l'utilisation de la pile pour chaque tâche et la quantité d'espace libre disponible. Vérification de ces données après une course de 24 heures avec beaucoup d'interaction utilisateur nous donne une certaine confiance que les allocations de pile définies sont « sans danger ».

Cela fonctionne en utilisant la technique bien essayé de remplir les piles avec un motif connu et en supposant que la seule façon que cela peut être réécrite est par l'utilisation de la pile normale, bien que si elle est en cours d'écriture par tout autre moyen d'une pile débordement est le moindre de vos soucis!

Answer 8

Nous avons essayé de résoudre ce problème sur un système embarqué à mon travail. Il est devenu fou, il y a juste trop de code (nos propres cadres et 3ème partie) pour obtenir une réponse fiable. Heureusement, notre appareil a été basé sur Linux pour que nous retombés au comportement standard de donner à chaque 2MB de fil et de laisser le gestionnaire de mémoire virtuelle optimiser l'utilisation.

Notre un problème avec cette solution a été l'un des outils 3ème partie effectué une mlock sur son espace mémoire complet (idéalement pour améliorer les performances). Cela a causé tous les 2 Mo de pile pour chaque fil de ses fils (75-150 d'entre eux) à paginée. Nous avons perdu la moitié de notre espace mémoire pour jusqu'à ce que nous l'ont vu et commenté la ligne incriminée.

Sidenote: gestionnaire de mémoire virtuelle de Linux (de VMM) alloue RAM en 4k morceaux. Lorsqu'un nouveau thread demande 2 Mo d'espace d'adresses pour sa pile, l'attribue VMM pages de mémoire à tous, mais faux le plus haut sommet page. Lorsque la pile grossit dans la page le noyau bogus détecte un défaut de page et permute la page avec un faux vrai, (qui consomme une autre 4K de RAM réelle). De cette façon, la pile d'un fil peut atteindre une taille dont il a besoin (aussi longtemps qu'il est moins de 2 Mo) et le VMM assurera seulement une quantité minimale de mémoire est utilisée.

Answer 9

En dehors de quelques-unes des suggestions déjà fait, je voudrais souligner que, souvent, dans les systèmes embarqués, vous devez contrôler étroitement l'utilisation de la pile parce que vous devez garder la taille de la pile à une taille raisonnable.

Dans un sens, en utilisant l'espace de pile est un peu comme l'allocation de mémoire, mais sans (facile) façon de déterminer si votre allocation a réussi afin de ne pas contrôler l'utilisation de la pile se traduira par une lutte pour toujours à comprendre pourquoi votre système se bloque à nouveau. Ainsi, par exemple, si votre système alloue de la mémoire pour les variables locales de la pile, soit allouer cette mémoire avec malloc () ou, si vous ne pouvez pas utiliser malloc () écrire votre propre gestionnaire de mémoire (ce qui est une tâche assez simple).

Non-no:

void func(myMassiveStruct_t par)
{
  myMassiveStruct_t tmpVar;
}

Oui-oui:

void func (myMassiveStruct_t *par)
{
  myMassiveStruct_t *tmpVar;
  tmpVar = (myMassiveStruct_t*) malloc (sizeof(myMassicveStruct_t));
}

semble assez évident, mais est souvent -. Surtout quand vous ne pouvez pas utiliser malloc ()

Bien sûr, vous aurez toujours des problèmes, donc c'est juste quelque chose pour aider, mais ne résout pas votre problème. cependant, il vous aidera à estimer la taille de la pile à l'avenir, car une fois que vous avez trouvé une bonne taille pour vos piles et si vous puis, après quelques modifications de code, exécutez à nouveau hors de l'espace de pile vous permet de détecter un certain nombre de bugs ou d'autres problèmes (piles appel trop profond pour un).

Answer 10

Pas 100% sûr, mais je pense que cela peut aussi être fait. Si vous avez un port JTAG exposé, vous pouvez vous connecter à Trace32 et vérifier l'utilisation maximale de la pile. Bien que pour cela, vous devrez donner une assez grande taille de la pile arbitraire initial.