Puis-je écrire une application C sans utiliser le tas?

Question

J'éprouve ce qui semble être une collision pile / tas dans un environnement intégré (voir cette question pour un peu de fond).

J'aimerais essayer de réécrire le code afin qu'il n'alloue pas de mémoire sur le tas.

Puis-je écrire une application sans utiliser le tas en C? Par exemple, comment n’utiliserais-je la pile que si j’ai besoin d’une allocation de mémoire dynamique?

Answer 1

Je l’ai fait une fois dans un environnement embarqué où nous écrivions "super safe". code pour les machines biomédicales. Les Malloc () s étaient explicitement interdites, en partie pour les limites de ressources et pour le comportement inattendu que vous pouvez obtenir avec la mémoire dynamique (cherchez malloc (), VxWorks / Tornado et la fragmentation et vous aurez un bon exemple).

Quoi qu’il en soit, la solution consistait à planifier à l’avance les ressources nécessaires et à allouer de manière statique le paramètre "dynamique". ceux dans un vecteur contenu dans un module séparé, ayant une sorte d’allocateur à usage spécial donner et reprendre des pointeurs. Cette approche évitait complètement les problèmes de fragmentation et permettait d'obtenir des informations d'erreur plus détaillées si une ressource était épuisée.

Cela peut sembler idiot sur un gros fer, mais sur des systèmes embarqués, et en particulier sur des systèmes critiques pour la sécurité, il est préférable d’avoir une très bonne compréhension des ressources en temps et en espace nécessaires à l’avance, ne serait-ce que pour le dimensionnement le matériel.

Answer 2

Curieusement, j’ai déjà vu une application de base de données qui reposait entièrement sur de la mémoire allouée statique. Cette application avait une forte restriction sur la longueur des champs et des enregistrements. Même l'éditeur de texte intégré (je frissonne encore en l'appelant ainsi) était incapable de créer des textes de plus de 250 lignes de texte. Cela a résolu une question que j’avais à l’époque: pourquoi ne permet-on que 40 enregistrements par client?

Dans les applications sérieuses, vous ne pouvez pas calculer à l'avance les besoins en mémoire de votre système en fonctionnement. Par conséquent, il est judicieux d’allouer de la mémoire dynamiquement selon vos besoins. Néanmoins, dans les systèmes embarqués, il est courant de préallouer la mémoire dont vous avez réellement besoin pour éviter les pannes inattendues dues à un manque de mémoire.

Vous pouvez allouer de la mémoire dynamique sur la pile à l'aide des appels de la bibliothèque alloca (). Mais cette mémoire est étroitement liée au contexte d’exécution de l’application et il est déconseillé de renvoyer une mémoire de ce type à l’appelant, car elle sera écrasée par les appels de sous-programmes ultérieurs.

Je pourrais donc répondre à votre question par un message clair et net "ça dépend" ...

Answer 3

Vous pouvez utiliser la fonction alloca () qui alloue de la mémoire sur la pile. Cette mémoire sera automatiquement libérée lorsque vous quitterez la fonction. alloca () est spécifique à GNU, vous utilisez GCC, il doit donc être disponible.

Voir man alloca .

Une autre option consiste à utiliser des tableaux de longueur variable, mais vous devez utiliser le mode C99.

Answer 4

Il est possible d'allouer une grande quantité de mémoire de la pile dans main () et de laisser votre code sous-allouer plus tard. C'est une bêtise à faire car cela signifie que votre programme utilise de la mémoire dont il n'a pas réellement besoin.

Je ne vois aucune raison (sauf une sorte de défi de programmation stupide ou d’exercice d’apprentissage) de vouloir éviter le tas. Si vous avez "entendu" & l'allocation de tas est lente et l'allocation de pile est rapide, c'est simplement parce que le tas implique une allocation dynamique . Si vous allouiez de manière dynamique de la mémoire à partir d'un bloc réservé dans la pile, ce serait tout aussi lent.

L'attribution de pile est simple et rapide, car vous ne pouvez désallouer le "plus jeune" " article sur la pile. Cela fonctionne pour les variables locales. Cela ne fonctionne pas pour les structures de données dynamiques.

Edit: Après avoir vu la motivation de la question ...

Premièrement, le tas et la pile doivent être en concurrence pour le même espace disponible. Généralement, ils se développent les uns envers les autres. Cela signifie que si vous déplacez d'une manière ou d'une autre toute votre utilisation du tas dans la pile, alors plutôt que d'entrer en collision avec un tas, la taille de la pile dépassera tout simplement la quantité de RAM disponible.

Je pense que vous devez simplement surveiller votre utilisation du tas et de la pile (vous pouvez utiliser des pointeurs sur des variables locales pour avoir une idée de l'état actuel de la pile) et la réduire si elle est trop haute. Si vous avez beaucoup de petits objets alloués de manière dynamique, n'oubliez pas que chaque allocation est surchargée en mémoire. Par conséquent, une sous-allocation à partir d'un pool peut aider à réduire les besoins en mémoire. Si vous utilisez la récursion n’importe où, pensez à la remplacer par une solution reposant sur un tableau.

Answer 5

Vous ne pouvez pas allouer de la mémoire dynamique en C sans utiliser de la mémoire de tas. Il serait assez difficile d'écrire une application du monde réel sans utiliser Heap. Au moins, je ne peux pas penser à un moyen de faire cela.

BTW, pourquoi voulez-vous éviter le tas? Quel est le problème avec elle?

Answer 6

1: Oui, vous le pouvez, si vous n'avez pas besoin d'allocation de mémoire dynamique, mais les performances de ce dernier pourraient être horribles, selon votre application. (c.-à-d. ne pas utiliser le tas ne vous donnera pas de meilleures applications)

2: Non, je ne pense pas que vous puissiez allouer de la mémoire de manière dynamique sur la pile, car cette partie est gérée par le compilateur.

Answer 7

Oui, c'est faisable. Décalez vos besoins dynamiques de la mémoire sur le disque (ou de tout stockage de masse disponible) et subissez les conséquences néfastes en termes de performances.

Exemple: vous devez créer et référencer un arbre binaire de taille inconnue. Spécifiez une structure d'enregistrement décrivant un nœud de l'arborescence, où les pointeurs sur d'autres nœuds sont en réalité des numéros d'enregistrement dans votre fichier d'arborescence. Écrivez des routines qui vous permettent d’ajouter à l’arborescence en écrivant un enregistrement supplémentaire dans un fichier et de parcourir l’arborescence en lisant un enregistrement, en trouvant son enfant sous un autre numéro d’enregistrement, en lisant cet enregistrement, etc.

Cette technique alloue de l’espace de manière dynamique, mais c’est l’espace disque, pas la RAM. Toutes les routines impliquées peuvent être écrites en utilisant un espace alloué de manière statique - sur la pile.

Answer 8

Les applications intégrées doivent faire attention à l'allocation de mémoire, mais je ne pense pas que l'utilisation de la pile ou de votre propre tas pré-alloué soit la solution. Si possible, allouez toute la mémoire requise (généralement des mémoires tampons et des structures de données volumineuses) au moment de l'initialisation à partir d'un segment de mémoire. Cela nécessite un style de programme différent de celui de la plupart d’entre nous, mais c’est le meilleur moyen de se rapprocher d’un comportement déterministe.

Un segment de mémoire volumineux sous-alloué ultérieurement risque toujours de manquer de mémoire. La seule chose à faire est alors de lancer un chien de garde (ou une action similaire). L'utilisation de la pile semble intéressante, mais si vous prévoyez d'allouer de grandes mémoires tampon / structures de données sur la pile, vous devez vous assurer que la pile est suffisamment grande pour gérer tous les chemins de code possibles que votre programme pourrait exécuter. Ce n'est pas facile et à la fin est similaire à un tas sous-alloué.

Answer 9

Ma principale préoccupation est la suivante: est-il vraiment utile d’abolir le tas?

Puisque vous souhaitez ne pas utiliser les segments de mémoire liés à une collision pile / segment de mémoire, en supposant que le début de la pile et le début du segment de mémoire sont correctement définis (par exemple, dans le même contexte, les petits exemples de programmes ne rencontrent pas ce problème de collision), la collision signifie le matériel n'a pas assez de mémoire pour votre programme.

En n'utilisant pas tas, on peut en effet économiser de l’espace perdu de la fragmentation du tas; mais si votre programme n'utilise pas le tas pour un tas d'allocation de grande taille irrégulière, le gaspillage y est probablement peu. Je verrai votre problème de collision davantage comme un problème de manque de mémoire, ce qui ne peut pas être résolu en évitant simplement le tas.

Mes conseils pour résoudre ce problème:

1. Calculez l'utilisation potentielle totale de la mémoire de votre programme. Si elle est trop proche de la quantité de mémoire que vous avez préparée pour le matériel, mais qu’elle n’excède pas encore celle-ci, vous pouvez alors
2. Essayez d’utiliser moins de mémoire (améliorez les algorithmes) ou d’utiliser la mémoire plus efficacement (par exemple, malloc () plus petit et de taille plus régulière pour réduire la fragmentation du tas); ou
3. Achetez simplement plus de mémoire pour le matériel

Bien sûr, vous pouvez essayer de tout insérer dans un espace mémoire statique prédéfini, mais il est très probable que la pile sera écrasée dans la mémoire statique cette fois-ci. Améliorez donc l'algorithme pour qu'il consomme moins de mémoire en premier et achetez plus de mémoire en second.

Answer 10

J'attaquerais ce problème d'une manière différente - si vous pensez que la pile et le tas entrent en collision, testez-le en vous protégeant.

Par exemple (en supposant un système * ix), essayez de mprotect () dans la dernière page de pile (en supposant une pile de taille fixe) afin qu'elle ne soit pas accessible. Ou - si votre pile augmente - alors mmap une page au milieu de la pile et de la pile. Si vous voyez un segv sur votre page de garde, vous savez que vous avez épuisé toute la pile. et en regardant l’adresse de la faute seg, vous pouvez voir laquelle de la pile & amp; tas sont entrés en collision.

Answer 11

Il est souvent possible d'écrire votre application intégrée sans utiliser l'allocation de mémoire dynamique. Dans de nombreuses applications intégrées, l'utilisation de l'allocation dynamique est déconseillée en raison des problèmes pouvant survenir en raison de la fragmentation de tas. Au fil du temps, il est très probable qu'il n'y aura pas de zone d'espace mémoire libre de taille appropriée pour permettre à la mémoire d'être allouée et, à moins qu'un système ne soit en place pour gérer cette erreur, l'application se bloquera. Il existe différents systèmes pour contourner ce problème, l'un consistant à toujours allouer des objets de taille fixe sur le tas afin qu'une nouvelle allocation tienne toujours dans une zone mémoire libérée. Un autre moyen de détecter l’échec de l’allocation et d’exécuter un processus de défragmentation sur tous les objets du tas (un exercice pour le lecteur!)

Vous ne dites pas quel processeur ou jeu d'outils vous utilisez, mais dans de nombreux cas, statique, tas et pile sont alloués à des segments définis distincts dans l'éditeur de liens. Si tel est le cas, votre pile grandit alors en dehors de l’espace mémoire que vous avez défini. La solution dont vous avez besoin consiste à réduire la taille de la pile et / ou de la variable statique (en supposant que ces deux valeurs soient contiguës), de manière à disposer de davantage de ressources pour la pile. Il peut être possible de réduire le tas de façon unilatérale, bien que cela puisse augmenter la probabilité de problèmes de fragmentation. En vous assurant qu'il n'y a pas de variables statiques inutiles, vous gagnerez de l'espace au prix d'une éventuelle augmentation de l'utilisation de la pile si la variable est rendue automatique.