Announcement: there is an English version of this forum on Moin, Ich stoße für ein Projekt mit ATMEGA328 an die RAM-Grenze von 2k. Mit avr-size und avr-nm kann ich zwar alle globalen Referenzen und deren Größe erfassen aber eben nicht all die localen statischen Variablen. Weil ich einige andere Libraries nutze ( z.B. elm ) und ist es sehr mühsam nun jede Funktion auf dessen lokale Variablen und deren Größe hin zu untersuchen. Mit allen lib´s sind ja schon immerhin 8200 Zeilen... :-( Gibt es ein schickes kleines Tool was z.B. den C-Quellcode dahingehend durchsucht? Andererseitz scheue ich mich etwas malloc() und free()zu nutzen weil ich keine Ahnung habe in wie weit das Performance kostet. Zumal ich mich zu erinnern meine, das bei großen Systemen malloc() zunächst immer n pages läd und diese dann zuteilt. In diesem Falle wüsste ich dann nun gar nicht mehr wieviel RAM zum Zeitpunkt X überhaupt noch zur Verfügung steht. Und dann ist es ja auch angesagt nur so 90% zu nutzen damit der Stack noch etwas wachsen kann. Beste Grüße Karsten
Ich hab mir mal ne Funktion geschrieben, um beim AVR-GCC zur Laufzeit die Stackauslastung zu ermitteln:
1 | #include <avr/io.h> |
2 | |
3 | #define FREE_MARK 0x77
|
4 | |
5 | extern uint8_t __bss_end; // lowest stack address |
6 | |
7 | extern uint8_t __stack; // highest stack address |
8 | |
9 | uint16_t stack_size( void ) // available stack |
10 | {
|
11 | return (uint16_t)&__stack - (uint16_t)&__bss_end + 1; |
12 | }
|
13 | |
14 | uint16_t stack_free( void ) // unused stack since last call |
15 | {
|
16 | uint8_t flag = 1; |
17 | uint16_t i, free = 0; |
18 | uint8_t * mp = &__bss_end; |
19 | |
20 | for( i = SP - (uint16_t)&__bss_end + 1; i; i--){ |
21 | if( *mp != FREE_MARK ) |
22 | flag = 0; |
23 | free += flag; |
24 | *mp++ = FREE_MARK; |
25 | }
|
26 | return free; |
27 | }
|
Wieso nimmt du nicht einfach einen Controller mit 4kb Ram?
Karsten K. schrieb: > Mit > avr-size und avr-nm kann ich zwar alle globalen Referenzen und deren > Größe erfassen aber eben nicht all die localen statischen Variablen. Nana... Da haste was falsch verstanden, glaube ich. Die lokalen statischen, werden zusammen mit den Globalen erfasst. Die sieht man also in der Liste.
Karsten K. schrieb: > vr-size und avr-nm kann ich zwar alle globalen Referenzen und deren > Größe erfassen aber eben nicht all die localen statischen Variablen. Statische lokale Variablen kommen ins data- oder bss-Segment. und werden daher von avr-size mit erfasst. Die nicht-statischen landen auf dem Stack oder in Registern, das kann kein Tool so ohne weiteres aus dem Quelltext ermitteln. Das braucht den Ansatz von Peter. Stringkonstanten und sonstige konstanten Daten sind aber schon alle im Flash, oder? Oliver
Karsten K. schrieb: > Mit avr-size und avr-nm kann ich zwar alle globalen Referenzen und deren > Größe erfassen aber eben nicht all die localen statischen Variablen. Die lokalen statischen Variablen landen wie globale Variablen auch in .data, wenn sie einen initialen Wert haben oder sie landen in .bss, wenn sie keinen initialen Wert haben. Das einzige was dir avr-size nicht anzeigen kann ist der Verbrauch durch Variablen die auf dem Stack landen. Karsten K. schrieb: > Gibt es ein schickes kleines Tool was z.B. den C-Quellcode dahingehend > durchsucht? Es gibt ein Perl-Skript, welches die .su-Dateien auswertet, welche der GCC mit -fstack-usage erzeugt: https://dlbeer.co.nz/oss/avstack.html
Oliver S. schrieb: > Stringkonstanten und sonstige konstanten Daten sind aber schon alle im > Flash, oder? Ich wette mal: nein.
Karsten K. schrieb: > Andererseitz scheue ich mich etwas malloc() und free()zu nutzen Malloc braucht man nur dann, wenn alloziierter Speicher über den Erzeuger hinaus weiter belegt bleiben soll. Es kostet zusätzlich zu jedem Speicherblock noch etwas Verwaltungsplatz. Malloc kann keinen Speicher hervorzaubern, es knappst ihn einfach vom Stack ab.
Du könntest den Projektordner in einen ordentlichen Texteditor laden (ich nehm gern Notepad++ [kostenlos]) und dann Innerhalb des Ordners nach allen Zeilen Suchen die mit einer typdef beginnen (und per regex kannste sogar functionen anhand der Klammer ausschliessen wenn Du magst) der gibt Dir dann alle Treffer und deren Anzahl zurück. danach brauchst Du nur die Ergebnissliste zu überfliegen (um multi inits zu erkennen) Und schon reicht der Taschenrechner um eine Abschätzung der Maximalwerte zu bekommen. avrstudio 'optimiert' aber unbenutzte Variablen vom Tisch soweit ich weiss und deren Speicherplatz ist dann irrelevant. Aber man hat wenigstens eine Übersicht in der man sich bequem umsehen kann, bleibt natürlich alles händische Arbeit leider. Für Laufzeitgrössen braucht es dann Codeflowdiagramme oder mindestens Aufrufketten (ich meine da gäbe es ein np++ plugin zu sogar kopfkratz) ist aber auch hier alles nur Hinweis und erleichterung, keine verlässliche Automatisierung :( 'sid
Arduino Fanboy D. schrieb: > Die lokalen statischen, werden zusammen mit den Globalen erfasst. > Die sieht man also in der Liste. Er hat kein Gegenteil behauptet. Karsten K. schrieb: > und ist es sehr > mühsam nun jede Funktion auf dessen lokale Variablen und deren Größe hin > zu untersuchen. Mit allen lib´s sind ja schon immerhin 8200 Zeilen... Gibt es da keine MAP files wie bei GCC, man könnte zumidest nach Files sortiert angucken, wo am meisten RAM gefressen wird und dann die Files genauer anschauen.
A. F. schrieb: > Er hat kein Gegenteil behauptet. Nein? Karsten K. schrieb: > ich zwar alle globalen Referenzen und deren > Größe erfassen aber eben nicht all die localen statischen Variablen. Sieht für mich aber doch schon so aus.
A. F. schrieb: > Gibt es da keine MAP files wie bei GCC, Wenn da schon avr-size und avr-nm werkeln, dann auch ein avr-gcc. Oliver
sid schrieb: > avrstudio 'optimiert' aber unbenutzte Variablen vom Tisch soweit ich > weiss > und deren Speicherplatz ist dann irrelevant. avrstudio optimiert überhaupt nichts. Das macht der GCC. sid schrieb: > Für Laufzeitgrössen braucht es dann Codeflowdiagramme oder mindestens > Aufrufketten Der call-graph kommt, in der von mir verlinkten Lösung mit dem Perl-Script, aus dem Disassembly des Binaries (objdump). Andere Compiler können den call-graph direkt erstellen, z.B. Clang. Manuell, d.h. ohne Hilfe des Compilers, einen call-graph aus dem C code zu erstellen halte ich für nicht sehr zweckmäßig, weil zu aufwändig und zu ungenau (Stichwort "inlining"). Dann lieber gleich mit dem Dissasembly arbeiten. Die Ungenauigkeiten wegen inlinings gelten jedoch auch da. Es hat schon seinen Grund warum professionelle Tools zur Ermittlung des exakten Stackbedarfs einen Haufen Geld kosten. Die von mir verlinkte Lösung ist eben auch nur eine Hosenträgerhilfskonstruktion und man sollte die Ergebnisse mit einer Priese Salz genießen. Dafür ist sie halt kostenlos.
sid schrieb: > typdef 1) Das heisst "typedef" ... und 2) hat mit dem Speicherverbrauch genau nichts zu tun leo
Christopher J. schrieb: > Die von mir verlinkte Lösung ist > eben auch nur eine Hosenträgerhilfskonstruktion und man sollte die > Ergebnisse mit einer Priese Salz genießen. Dafür ist sie halt kostenlos. Ernstgemeinte Frage, weil mich das Thema sehr interessiert: In der Praxis will ich ja bloß wissen, ob die Ressourcen des Prozessors für mein Programm sicher reichen. Den statischen Speicherbedarf sagt mit Atmel Studio nach dem Linken. Den Stack könnte ich wie von peda vorgeschlagen überwachen. Bringt mir das Hosenträgertool weitere Erkenntnisse? Oder ist es bloß umständlicher?
Peter D. schrieb: > Ich hab mir mal ne Funktion geschrieben, um beim AVR-GCC zur Laufzeit > die Stackauslastung zu ermitteln: Es sollte auch gehen, die worst-case Stackauslastung zur (eigentlich nach der) Compilezeit zu ermitteln. Allerdings nicht für jedes Programm. Sobald irgendwas rekursiv aufgerufen wird oder indirekte Sprünge bzw. Unterprogrammaufrufe verwendet werden, geht's nicht mehr, jedenfalls nicht durch automatische Analyse des Maschinencodes. Mit den Informationen, die der Compiler zusätzlich besitzt, sollte sich allerdings auch noch das Problem der Indirektionen eleminieren lassen (natürlich nur für fehlerfreien Code und ohne eingebundene Binaries). Was allerdings prinzipiell nicht lösbar ist, ist das das Problem der Rekursion. Alles, was hier möglich ist, ist die Erkennung der Rekursion. Und selbst die ist recht teuer.
* Worst-case Stackauslastung, zur Laufzeit bestimmt: https://rn-wissen.de/wiki/index.php?title=Speicherverbrauch_bestimmen_mit_avr-gcc#Dynamischer_RAM-Verbrauch Der Code ist ähnlich wie der von PeDa. Er bestimmt die worst-case Auslastung für einen konkreten Lauf, inclusive Bedarf ausgeführter ISRs. Problem: So lässt sich nur eine untere Grenze des RAM- bzw. Stack-Verbrauchs bestimmen, was man aber braucht für wasserdichte Robustheit ist eine obere Grenze. Problem: Nicht kompatibel mit malloc (gilt genauso für PeDas Ansatz). * Worst-case Stackauslastung zu Laufzeit, per statischer Analyse bestimmt. Hierfür gibt es Tools, die per abstrakter Interpretation eine obere Grenze des Stack-Verbrauchs bestimmen und versuchen, diese Grenze möglichst klein zu halten. Problem: Komplexe Analyse bei Rekursion, indirekten Funktionsaufrufen (virtual Functions) und dynamischer Speicherallokierung (malloc, alloca). Teilweise sind Annotations in der Quelle erforderlich (etwa bei Tools von AbsInt, die aber m.W. nicht für AVR verfügbar sind sondern eher in Avionik, Nukleartechnik etc. eingesetzt werden). Problem: Für Analyse von Interrupts (auch für WCET, also Worst Case Execution Time mit Interrupts) sind weitere Tools erforderlich. Inline-Funktionen sind übrigens kein Problem. Inlining vereinfacht nämlich den dynamischen Call-Tree. Was Stack-Auslastung angeht wird die statische / abstrakte Analyse dadurch ebenfalls einfacher. Der statische Stack-Bedarf einer Funktion ist ja bekannt (außer bei alloca(), was aber eher selten eingesetzt wird), und wenn er durch Inlining steigt, geht das in die Analyse mit ein. Auch hier gilt: gebraucht wir nicht die exakte Stack-Auslastung, sondern eine möglichst kleine obere Schranke. Optimalerweise stimmt diese Schranke mit dem wirklichen Maximum überein, aber gerade bei komplexen Programmen wird die Schranke größer sein als das Maximum. Wichtig ist, dass es eine obere Schranke ist und nicht eine untere Schranke, wie man sie etwa durch Simulation(en) oder das obige get_mem_unused() erhält. Mit Simulation(en) oder Bestimmung(en) zur Laufzeit muss man dann nachweisen, dass der so erhaltene Wert mit dem maximalen Verbrauch übereinstimmt. Für einfache Programme ist das durchaus machbar.
:
Bearbeitet durch User
c-hater schrieb: > Was allerdings prinzipiell nicht lösbar ist, ist das das Problem der > Rekursion. Das ist nicht prinzipiell unlösbar, siehe Abstrakte Analyse. Das ist natürlich teuer — sowohl was die eingesetzten Tools angeht als auch was die benötigte Analysezeit betrifft. Für komplexe Fälle ist natürlich Unterstützung durch Entwickler gefragt, z.B. durch Annotationen in der Quelle. Ansonsten hätte man das Halteproblem gelöst :-) Übrigens fällt bei Tools wie von AbsInt die Stack-Analyse quasi als Beifang der wesentlich aufwändigeren WCET-Analyse an.
Dieter R. schrieb: > Den Stack könnte ich wie von peda vorgeschlagen überwachen. > > Bringt mir das Hosenträgertool weitere Erkenntnisse? Oder ist es bloß > umständlicher? Statische Analysetools wie das Skript von Daniel Beer geben eine Abschätzung des benötigten Stack nach oben, d.h. man kann (wenn das Werkzeug korrekt funktioniert) sicher sein, dass das Programm mit soundsoviel Speicher auskommt. Diese Abschätzung ist für gewöhnlich (mitunter deutlich) größer als das was das Programm tatsächlich benötigt. Laufzeitanalysen wie die Funktion von Peda geben immer nur eine Abschätzung nach unten, d.h. man weiß, dass das Programm mindestens diesen Stack benötigt. Es gibt auch die Möglichkeit diese Abschätzung mittels eines Pattern zu machen, was man im RAM an die Stelle schreibt, wo später mal der Stack landet. Dann lässt man das Programm laufen und schaut sich später an bis wohin dieses Pattern (z.B. 0xDEADBEEF) vom Stack überschrieben wurde. Wenn man dann noch nachweisen kann, dass alle möglichen Pfade des Programms durchlaufen wurden, dann hat man damit auch eine obere Grenze für den benötigten Stack. Dieser Nachweis ist aber alles andere als trivial. PS: Johann war schneller ;)
:
Bearbeitet durch User
Dieter R. schrieb: > In der Praxis will ich ja bloß wissen, ob die Ressourcen des Prozessors > für mein Programm sicher reichen. [...] Den Stack könnte ich wie von > peda vorgeschlagen überwachen. Nein, siehe oben. Solche Ansätze liefern prinzipbedingt nur eine untere Schranke des Verbrauchs, und das bleibt auch so wenn man das Maximum über mehrere Läufe bildet. Dafür, ob es sicher recht, brauch man aber eine obere Schranke.
Johann L. schrieb: > Problem: Komplexe Analyse bei Rekursion Die immer dann scheitern wird, wenn das Eintreten der Abbruchbedingung für die Rekursion zur Entwurfszeit unbekannt ist. Blöderweise sind aber gerade diese Fälle genau die, die überhaupt zum Einsatz rekursiver Algorithmen animieren. Die einzige Lösung zur Begrenzung ist dann ein fixe Schranke für die Rekursionstiefe. Sieht man diese vor, ist aber wiederum keine Rekursion mehr nötig, man kann die Sache dann immer in eine Schleife umformen. Sprich: Eine "komplexe Analyse bei Rekursion" kann man sich prinzipiell schenken. Es genügt, die Rekursion zu erkennen. Soll der Programmierer doch den Kram in eine Schleife umformen. Ist sowieso immer die effizientere Lösung, weil der Callframe wegfällt.
Johann L. schrieb: > Der statische Stack-Bedarf einer Funktion ist ja bekannt (außer bei > alloca(), was aber eher selten eingesetzt wird), und wenn er durch > Inlining steigt, geht das in die Analyse mit ein. Stimmt, da hatte ich einen Denkfehler. Hatte fälschlicherweise angenommen der zusätzliche Bedarf würde nicht in die Analyse eingehen und die Analyse des Disassembly dann noch den call "übersehen" (weil nicht vorhanden) aber der zusätzliche Verbrauch durch inlining geht natürlich mit ein.
Moin Moin, Vielen Herzlichen Dank für all euren Input. Das muss ich jetzt erst einmal alles lesen. Meega Danke! Aber schon mal kurz: ... und Ja, ich habe natürlich schon alle Stringkonstanten und Sonstiges im Flash ( Wette Verloren ) :-) .. und einfach einen 4k AVR nehmen ist Gut aber ein 64Pin großes Teil ist mir zu groß. Und es muss auch noch irgendwie lötbar bleiben; also kein 05 Pitch oder so. Zumal es nicht die Ursache bekämpft. .. und ich nutze avr-gcc mit make und vi; IDE´s sind "Teufelswerk" :-) .. und sicher zeigt avr-size auch die lokalen Variablen in Summe mit an. Das nützt aber nur bedingt als das ich nicht weiß in welcher funktion RAM verschwendet wird. .. und malloc() würde Sinn machen wenn der allokierte Speicher natürlich via pointer weitergereicht wird. Die Frage war aber ob die Implementierung von malloc() für einen AVR eben nicht ganze Pages ( wie groß diese auch sein mögen ) allokiert. Denn dann wäre mit einem p = malloc(10); eventuell eben nicht 10Byte sondern vielleicht 32Byte reserviert. Gruß Karsten
Markiere beim Programmstart den ganzen freien Speicher mit einem festen Wert, den du später wieder erkennst. z.B. 0x55. Dann lässt du das Programm eine weile laufen, und schaust mit dem Debugger das Ergebnis an. DU kannst dann sehen, wie viel RAM bis dahin ungenutzt blieb.
Karsten K. schrieb: > .. und einfach einen 4k AVR nehmen ist Gut aber ein 64Pin großes Teil > ist mir zu groß. Nimm einen Mega1284P. Der hat 16k SRAM und es gibt ihn im absolut bastlertauglichen DIP40-Gehäuse.
Eine pragmatische "Arme-Leute"-Variante, die noch nicht genannt wurde: im Gegensatz zu (den meisten) PC-Anwendungen, die wenig Einfluß auf die Stackgröße lassen, ist man ja beim µC vollkommen Herr darüber. Kann den also auch mal "unvernünftig klein" machen. Wenn man bei ausgiebigen Tests mit kleinen Stack und einem simplen Stack-Guard keine Überschreiber feststellt und anschliessend den Stack einfach deutlich vergrössert (je nach Platz verdoppelt oder halt der restlich verbliebene Speicher), sollte ein Laufzeitproblem so gut wie ausgeschlossen sein.
:
Bearbeitet durch User
Stefanus F. schrieb: > Markiere beim Programmstart den ganzen freien Speicher mit einem festen > Wert, den du später wieder erkennst. z.B. 0x55. Dann lässt du das > Programm eine weile laufen, und schaust mit dem Debugger das Ergebnis > an. DU kannst dann sehen, wie viel RAM bis dahin ungenutzt blieb. Siehe Johann L. schrieb: > * Worst-case Stackauslastung, zur Laufzeit bestimmt: > > https://rn-wissen.de/wiki/index.php?title=Speicherverbrauch_bestimmen_mit_avr-gcc#Dynamischer_RAM-Verbrauch Christopher J. schrieb: > Es gibt auch die Möglichkeit diese Abschätzung > mittels eines Pattern zu machen, was man im RAM an die Stelle schreibt, > wo später mal der Stack landet. Dann lässt man das Programm laufen und > schaut sich später an bis wohin dieses Pattern (z.B. 0xDEADBEEF) vom > Stack überschrieben wurde. Wenn man dann noch nachweisen kann, dass > alle möglichen Pfade des Programms durchlaufen wurden, dann hat man > damit auch eine obere Grenze für den benötigten Stack. Falls damit Code-Abdeckung (Code Coverage) gemeint ist: Diese genügt i.A. nicht für den Nachweis, dass es eine obere Grenze ist: Code Coverage ist nicht hinreichend für WCSU (Worst Case Stack Usage). Beispiel:
1 | funcX (x): |
2 | funcs = { func0, func1 } |
3 | |
4 | funcs[x]() // call func0 or func1 |
5 | |
6 | func0 (): |
7 | func1() |
8 | |
9 | func1 (): |
10 | // do something
|
11 | |
12 | main: |
13 | x = input() // x = 1 |
14 | func0() // Covers: func0, func1, call depth = 2 |
15 | funcX(x) // Covers: funcX, func1, call depth = 2 |
16 | // Now we have covered all the program but with
|
17 | // x = 0 we get: funcX -> func0 -> func1, call depth = 3
|
Hier wird der komplette Code per x = 1 abgedeckt und liefert eine Call-Tiefe von 2. x = 0 jedoch gibt eine Call-Tiefe von 3 und damit einen Wert über dem für komplett abgedeckten Code. Das Beispiel braucht weder Schleifen noch Rekursion. Meine Intuition sagt, dass es auch zusätzlich ohne indirekte Funktionsaufrufe geht.
:
Bearbeitet durch User
Christopher J. schrieb: > avrstudio optimiert überhaupt nichts. Das macht der GCC. > Ja hast recht, ist aber Haarspalterei; denn GCC optimiert ja nur weil avrstudio darum bittet ;) und letzenendes ist ja nur die Frage OB der kompilierte code derart optimiert ist oder nicht um die Frage zu beantworten ob der atmega "voll" ist oder nicht ;) > Der call-graph kommt, in der von mir verlinkten Lösung mit dem > Perl-Script, aus dem Disassembly des Binaries (objdump). Andere Compiler > können den call-graph direkt erstellen, z.B. Clang. Manuell, d.h. ohne > Hilfe des Compilers, einen call-graph aus dem C code zu erstellen halte > ich für nicht sehr zweckmäßig, weil zu aufwändig und zu ungenau > (Stichwort "inlining"). Dann lieber gleich mit dem Dissasembly arbeiten. > Die Ungenauigkeiten wegen inlinings gelten jedoch auch da. Es hat schon > seinen Grund warum professionelle Tools zur Ermittlung des exakten > Stackbedarfs einen Haufen Geld kosten. Die von mir verlinkte Lösung ist > eben auch nur eine Hosenträgerhilfskonstruktion und man sollte die > Ergebnisse mit einer Priese Salz genießen. Dafür ist sie halt kostenlos. Ich meinte bloss für ne "Übersicht" reicht selbst der Ablauf von... kA Doxygen oder so... aber klar, wenn man es absolut 100% genau wissen will, dann geht das nichtmehr mit nem texteditor. Aber ganz ehrlich ich hab noch keinen 2k atmega code gesehen dem man nicht auch noch 'mit dem Auge' hätte folgen können und darum ging es doch wohl hier. leo, du bist n Quatschkopp ;) typen (singular: typ) sind entweder von Dir selbst definiert
1 | typedef uint8_t Pfrz; |
suchen musste nach allen typ Definitionen (typdef weil ich zu faul zum tippen bin) Aber klar typedefs müssen da natürlich inkludiert sein (structs zB;)) 'sid
Markus F. schrieb: > Eine pragmatische "Arme-Leute"-Variante, die noch nicht genannt wurde: > > im Gegensatz zu (den meisten) PC-Anwendungen, die wenig Einfluß auf die > Stackgröße lassen, ist man ja beim µC vollkommen Herr darüber. Kann den > also auch mal "unvernünftig klein" machen. > > Wenn man bei ausgiebigen Tests mit kleinen Stack und einem simplen > Stack-Guard keine Überschreiber feststellt und anschliessend den Stack > einfach deutlich vergrössert (je nach Platz verdoppelt oder halt der > restlich verbliebene Speicher), sollte ein Laufzeitproblem so gut wie > ausgeschlossen sein. OMG Hoffentlich bist du nicht für die Sicherheit irgendeiner Anwendung verantwortlich...
sid schrieb: > leo, du bist n Quatschkopp ;) > typen (singular: typ) sind entweder von Dir selbst definierttypedef > uint8_t Pfrz; Wie faseln? Ein typedef definiert eine Typ. Ob der verwendet wird oder nicht und ob eine Variable damit benutzt wird ist wahlfrei. Daher koennen z.b. beliebige typedef's herumstehen ohne dass jemals ein Byte Speicher verbraucht wird oder umgekehrt ich verzichte ganz auf typedefs und die Variablen brauchen trotzdem ihren Platz. Die Analyse der typedefs ist aber notwendig, um den Speicherverbrauch von Variablen zu untersuchen, wenn sie typedef verwenden. leo
Johann L. schrieb: > Meine Intuition sagt, dass es auch zusätzlich ohne indirekte > Funktionsaufrufe geht.
1 | funA (x): |
2 | funB (x) |
3 | |
4 | funB (x): |
5 | if x != 0 |
6 | funC() |
7 | |
8 | funC(): |
9 | // do domething
|
10 | |
11 | main: |
12 | x = input() // x = 1 |
13 | funB(x) // Covers funB (case x != 0), funC; call depth = 2 |
14 | funA(x-1) // Covers funB (case x == 0), funA; call depth = 2 |
15 | // Now we covered all the code and have call depth = 2.
|
16 | // But x = 2 will call funA(2) -> funB(2) -> funC, call depth = 3
|
Auch hier ist mit x = 1 die Call-Tiefe 2 bei komplett überdecktem Code. Für x = 2 hat man jedoch Call-Tiefe 3. Keine Schleifen, keine Rekursion, keine indirekten Funktionsaufrufe, keine dynamische Speicherallokierung.
Karsten K. schrieb: > Die Frage war aber ob die > Implementierung von malloc() für einen AVR eben nicht ganze Pages ( wie > groß diese auch sein mögen ) allokiert. Denn dann wäre mit einem p = > malloc(10); eventuell eben nicht 10Byte sondern vielleicht 32Byte > reserviert. Der AVR ist ein 8-Bit-Prozessor... Die avrlibc-Standardversion von malloc braucht eine paar Bytes zur Verwaltung, und dazu ein Byte pro Block. Wie aber schon gesagt wurde, macht das den Speicher auch nicht größer. Markus F. schrieb: > im Gegensatz zu (den meisten) PC-Anwendungen, die wenig Einfluß auf die > Stackgröße lassen, ist man ja beim µC vollkommen Herr darüber. Kann den > also auch mal "unvernünftig klein" machen. Genau wie bei allen PC- und auch Mikrocontrolleranwendungen ohne Betriebssystem ist der Stack im AVR immer genau so groß, wie gerade groß ist. Und da es davon auch nur genau einen gibt, kann man den weder „vernünftig“ noch „unvernünftig“ kleiner oder größer machen. Wenn SRAM voll, dann SRAM voll. Oliver
:
Bearbeitet durch User
Karsten K. schrieb: > Das nützt aber nur bedingt als das ich nicht weiß in welcher funktion > RAM verschwendet wird. Das Stichwort map-file ist ja schon gefallen. Aber mal ganz ernsthaft, ohne große Arrays bekommt man 2k Ram doch gar nicht so einfach voll. Und wo du welche verwendest, solltest du auch ohne mapfile-Analyse rausbekommen. Ich tippe immer noch auf Strings. Zeig doch mal etwas Beispielcode. Oliver
:
Bearbeitet durch User
Oliver S. schrieb: > Genau wie bei allen PC- und auch Mikrocontrolleranwendungen ohne > Betriebssystem ist der Stack im AVR immer genau so groß, wie gerade groß > ist. Und da es davon auch nur genau einen gibt, kann man den weder > „vernünftig“ noch „unvernünftig“ kleiner oder größer machen. > > Wenn SRAM voll, dann SRAM voll. Ja, klar. Der Trick ist, dafür zu sorgen, dass genau diese Situation garantiert niemals eintritt... Und das ist wirklich alles andere als einfach.
Karsten K. schrieb: > .. und einfach einen 4k AVR nehmen ist Gut aber ein 64Pin großes Teil > ist mir zu groß. Und es muss auch noch irgendwie lötbar bleiben; also > kein 05 Pitch oder so. Bei SDIP28 oder SO28 kannst Du auch z.B. einen PIC32MX170F256B-50I/SP (SDIP28) nehmen. 256k Flash, 64k RAM, 50MHz 32 Bit, und das ganze für aktuell 3.62€ bei Mouser z.B. Gibts aber auch bei Reichelt. Damit ist die Grenze ZIEMLICH weit nach oben gerutscht. fchk
Johann L. schrieb: >> Wenn man dann noch nachweisen kann, dass alle möglichen Pfade des >> Programms durchlaufen wurden, dann hat man damit auch eine obere Grenze >> für den benötigten Stack. > > Falls damit Code-Abdeckung (Code Coverage) gemeint ist: Diese genügt > i.A. nicht für den Nachweis, dass es eine obere Grenze ist: > > Code Coverage ist nicht hinreichend für WCSU (Worst Case Stack Usage). Mit "alle möglichen Pfade" meinte ich wirklich alle möglichen Pfade im Sinne eines call-graph und zusätzlich auch alle möglichen Verzweigungen innerhalb der einzelnen Funktionen. Das wäre dann im Sinne deines Beispiels:
1 | funA (x): |
2 | funB (x) |
3 | |
4 | funB (x): |
5 | if x != 0 |
6 | // do something complicated which requires a lot of stack space
|
7 | else
|
8 | return
|
9 | |
10 | main: |
11 | x = input() // x = 1 |
12 | funB(x-1) // Covers funB (case x == 0), early return; call depth = 1 |
13 | funA(x-1) // Covers funB (case x == 0), funA; call depth = 2 |
14 | // Now we covered every possible path in the call-graph
|
15 | // But x = 2 will call funA(1) -> funB(1) -> if clause is triggered and something complicated is calculated
|
Man muss also im Prinzip alle Funktionen auch mit allen möglichen Eingabewerten füttern, gewissermaßen wie bei einem Fuzzer.
:
Bearbeitet durch User
Christopher J. schrieb: > Johann L. schrieb: >>> Wenn man dann noch nachweisen kann, dass alle möglichen Pfade des >>> Programms durchlaufen wurden, dann hat man damit auch eine obere Grenze >>> für den benötigten Stack. >> >> Falls damit Code-Abdeckung (Code Coverage) gemeint ist: Diese genügt >> i.A. nicht für den Nachweis, dass es eine obere Grenze ist: >> >> Code Coverage ist nicht hinreichend für WCSU (Worst Case Stack Usage). > > Mit "alle möglichen Pfade" meinte ich wirklich alle möglichen Pfade im > Sinne eines call-graph und zusätzlich auch alle möglichen > Verzweigungen innerhalb der einzelnen Funktionen. Das wäre dann im Sinne > deines Beispiels: Selbst das reicht nicht aus, weil Funktionen nicht nur von ihren Argumenten abhängen, sondern auch von Speicherinhalten (auch SFRs und I/O). Eine Funktion kann sich zum Beispiel merken, wie oft sie aufgerufen wurde oder kann sich zu unterschiedlichen Zeiten (Timer) unterschiedlich verhalten. Aber selbst bei rein funktionaler Programmierung (in C: nur const Funktionen) ist das Verfahren i.d.R absolut inpraktikabel: Die Komplexität explodiert. Bei zwei 32-Bit Argumenten sind das schon 10^19 Fälle. Bei 4 GHz Takt und 1 Test pro Zyklus macht das 2.5·10^9 Sekunden = 80 Jahre. Außerdem muss man bei allen Funktionen wissen, welche Argumente zur Laufzeit (nicht) auftreten können / dürfen, damit man nix übersieht oder die Funktion abschmiert / ne Trap wirft bei der Analyse. Bei Teilfunktionen ist das oft schwer zu analysieren. Und dann bräuchte man auch Tools, die sowas unterstützen. Was gibt's denn da so?
:
Bearbeitet durch User
Karsten K. schrieb: > .. und ich nutze avr-gcc mit make und vi; IDE´s sind "Teufelswerk" :-) > .. und sicher zeigt avr-size auch die lokalen Variablen in Summe mit an. Nein, avr-size zeigt nur Daten im Static Storage, also keine auto-Variablen. -fstack-usage wurde schon genannt:
1 | void use (char*); |
2 | |
3 | void fun (void) |
4 | {
|
5 | char x[10]; |
6 | use (x); |
7 | }
|
mit avr-gcc -fstack-usage -fverbose-asm -save-temps == .su ==
1 | foo.c:3:6:fun 14 static |
== .s ==
1 | fun: |
2 | ... |
3 | /* prologue: function */ |
4 | /* frame size = 10 */ |
5 | /* stack size = 12 */ |
6 | .L__stack_usage = 12 |
7 | ... |
Es werden also "stack size" + 2 Bytes Stack gebraucht (2 Bytes für CALL). Bei -fstack-usage sieht man allerdins nicht die Größe des Frames. Dafür ist .su hilfreich um Verwendung von alloca() zu erkennen, was aus .s nicht an den Kommentaren ersichtlich ist:
1 | void fun_n (int n) |
2 | {
|
3 | char x[n]; |
4 | use (x); |
5 | }
|
== .su ==
1 | foo.c:9:6:fun_n 6 dynamic |
== .s ==
1 | fun_n: |
2 | ... |
3 | /* prologue: function */ |
4 | /* frame size = 0 */ |
5 | /* stack size = 4 */ |
6 | .L__stack_usage = 4 |
7 | ... |
> Das nützt aber nur bedingt als das ich nicht weiß in welcher funktion > RAM verschwendet wird. Einfach die asm-Kommentare oder .su mit Python o.ä. auswerten. > .. und malloc() würde Sinn machen wenn der allokierte Speicher > natürlich via pointer weitergereicht wird. Das kann mit jedem Speicher gemacht werden. Falls der Speicher nur lokal gebraucht wird, d.h. nicht nach Beenden der Funktion noch gebraucht wird, geht auch alloca(). Unterfunktionen sind kein Problem, siehe obiges Beispiel mit fun_n(). Beispiel ist Zusammenbau eines Strings für die Ausgabe. Entweder man nimmt einen statischen Puffer oder alloca(). Statischer Puffer ist einfacher aber nicht reentrant, und man muss die maximale Größe zur Compilezeit kennen. Nachteilig, wenn es mehrere Funktionen mit solchen statischen Puffern gibt: Diese belegen immer den Maximalplatz, auch wenn die verwendenden Funktionen nicht in der gleichen Call-Chain sind. alloca() benötigt etwas mehr Code, hat aber keinen Vorteil, wenn alle betroffenen Funktionen in der gleichen Call-Chain sind und das Maximum an jeweils benötigtem Speicher anfordern. Static Storage hat wiederum den Vorteil einfacher Analyse, avr-size reicht aus. Mit alloca() muss man mühsam Buchführung betreiben, was maximal auftreten kann (oder teure Tools nehmen). > Die Frage war aber ob die Implementierung von malloc() für einen > AVR eben nicht ganze Pages ( wie groß diese auch sein mögen ) > allokiert. Es wird mehr Speicher allokiert als gebraucht, und es wird eine Listenstruktur zur Verwaltung unterhalten. Zusätzlich können Probleme mit Speicherfragmentierung auftreten (was bei alloca() nicht der Fall ist, da sich alloca() wie eine lokale auto Variable verhält). Um welche Variablen / Objekte geht es denn?
Oliver S. schrieb: > Genau wie bei allen PC- und auch Mikrocontrolleranwendungen ohne > Betriebssystem ist der Stack im AVR immer genau so groß, wie gerade groß > ist. Und da es davon auch nur genau einen gibt, kann man den weder > „vernünftig“ noch „unvernünftig“ kleiner oder größer machen. Bei meinen Anwendungen ist der Stack genauso groß, wie ich ihn haben will. Die Welt besteht nicht nur aus AVRs.
Markus F. schrieb: > Die Welt besteht nicht nur aus AVRs. Mag sein, aber Karsten K. schrieb: > ATMEGA328 Deine Anwendungen spielen daher hier keine allzugroße Rolle. Oliver
Johann L. schrieb: > Selbst das reicht nicht aus, weil Funktionen nicht nur von ihren > Argumenten abhängen, sondern auch von Speicherinhalten (auch SFRs und > I/O). Eine Funktion kann sich zum Beispiel merken, wie oft sie > aufgerufen wurde oder kann sich zu unterschiedlichen Zeiten (Timer) > unterschiedlich verhalten. Ja, das stimmt. Dafür müsste man bei einem Embedded-System auch noch Fuzzing auf Hardwareebene betreiben. Johann L. schrieb: > Aber selbst bei rein funktionaler Programmierung (in C: nur const > Funktionen) ist das Verfahren i.d.R absolut inpraktikabel: > > Die Komplexität explodiert. Bei zwei 32-Bit Argumenten sind das schon > 10^19 Fälle. Bei 4 GHz Takt und 1 Test pro Zyklus macht das 2.5·10^9 > Sekunden = 80 Jahre. Ja, das ist schon klar. Mit "alle möglichen Eingabewerte" meinte ich eben alle möglichen Eingabewerte, welche zu unterschiedlichen Code-Verzweigungen führen. In dem Beispiel sind es ja nur zwei. In jedem Fall ist das ganze Unterfangen alles andere als trivial ;) Zurück zum eigentlichen Thema: Karsten K. schrieb: > .. und sicher zeigt avr-size auch die lokalen Variablen in Summe mit an. > Das nützt aber nur bedingt als das ich nicht weiß in welcher funktion > RAM verschwendet wird. Ok, das hatte ich so nicht ganz deinem Anfangsposting entnehmen können. Du hattest ja schon avr-nm erwähnt. Mit ein bisschen Kombination aus avr-readelf kann man da ganz vernünftige Übersichten mit bekommen. Es gibt sogar ein kleines Tool, was aber Windows-only ist und nach einem ersten Versuch auch nicht unter Wine läuft: https://github.com/govind-mukundan/MapViewer Dazu gibt es den passenden Artikel in dem beschrieben wird, wo das Tool seine Informationen herbekommt: https://www.embeddedrelated.com/showarticle/900.php Sicher könnte man da auch ein kleines Python- oder Perl-Script schreiben um die gleichen Informationen zu bekommen (ohne .Net).
Johann L. schrieb: > Falls damit Code-Abdeckung (Code Coverage) gemeint ist: Diese genügt > i.A. nicht für den Nachweis, dass es eine obere Grenze ist: > > Code Coverage ist nicht hinreichend für WCSU (Worst Case Stack Usage). Mal ne naive Frage. Wie wäre es, basierend auf den "Tricks" mit der Staclmessung einfach eine Testfunktion in die diversen Fuktionen einzubauen und dort regelmäßig zu messen und im Fehlerfall bzw. wenn es eng wird eine Debugmeldung zu erzeugen? Kostet nur ein paar Takte, bringt aber REALE Infos mit wenig Aufwand und ohne endloses Theoretisieren ;-)
Falk B. schrieb: > Wie wäre es, basierend auf den "Tricks" mit der Staclmessung einfach > eine Testfunktion in die diversen Fuktionen einzubauen und dort > regelmäßig zu messen und im Fehlerfall bzw. wenn es eng wird eine > Debugmeldung zu erzeugen? Meine Compiler hatten das als Feature: entweder kleiner Test vor jeder stackallokierung, oder z.b. beim Pic10..18 die komplette callgraph-vorwegbestimmung (ohne Rekursion und mit leichter Einschränkung bei Funktionspointern). PCLint kann das für viele Fälle auch sehr gut vorausberechnen.
Markus F. schrieb: > Kann den (Stack) also auch mal "unvernünftig klein" machen. Beim avr-gcc hat der Stack normalerweise ohnehin keine feste Größe. Er liegt im gleichen Speicherbereich, wie der Heap. Beide wachsen dynamisch aufeinander zu.
Oliver S. schrieb: > Ich tippe immer noch auf Strings. Besonders das Arduino Framework verleitet durch seine umfangreichen Möglichkeiten der String Klasse dazu, den Speicher ratz fatz voll zu machen oder zu fragmentieren.
Johann L. schrieb: > Problem: So lässt sich nur eine untere Grenze des RAM- bzw. > Stack-Verbrauchs bestimmen, was man aber braucht für wasserdichte > Robustheit ist eine obere Grenze. Die untere Grenze eignet sich aber zum Abschätzen, wie ausgelastet der SRAM ist. Insbesondere da der AVR keine nested Interrupts unterstützt, ist das schon ein guter Anhaltspunkt. Ich baue daher diese Routine oft mit ein. Die Ausgabe erfolgt z.B. über ein Kommando auf der Remote-Schnittstelle oder über eine Tastenkombination auf dem Display. Man kann den Worst-Case Wert aber auch im EEPROM speichern.
Peter D. schrieb: > Insbesondere da der AVR keine nested Interrupts unterstützt, Ich meine schon. Manche sogar mit Priorisierung.
Drei, unterwegs schrieb: > Peter D. schrieb: >> Insbesondere da der AVR keine nested Interrupts unterstützt, > > Ich meine schon. Manche sogar mit Priorisierung. Ja, das ist der Zeitgeist. MEINEN liegt voll im Trend, so wie vegane Ernaährung. Aber WISSEN wird mehr und mehr zur Mangelware. Nein, die normalen AVRs haben von Hause aus KEINE verschachtelten (neudeutsch nested) Interrupts. Bestenfalls die ATXmegas. Man kann sie aber per Software nachbilden, wenn man weiß was man tut.
Falk B. schrieb: > Nein, die normalen AVRs haben von Hause aus KEINE verschachtelten > (neudeutsch nested) Interrupts. Bestenfalls die ATXmegas. > Man kann sie aber per Software nachbilden, wenn man weiß was man tut. So what? Also unterstützen sie nested interupts ("unterstützen" im Sinne von: machen es möglich). Die Unterstützung erfolgt halt nur nicht direkt durch die Hardware und ist deshalb u.U. etwas ineffizient. Tatsächlich wird das aber nur dann zu einem echten Problem, wenn mehrere mit (potentiell) hoher Folgefrequenz aufgerufene Interrupts miteinander hakeln. Dann hast du aber bei echten Hardware-Interruptprioritäten ebenfalls ein Problem. Und dort ist es meist nicht so einfach, zu einer Lösung zu kommen, wie es das beim AVR8 ist, wo es recht einfach ist, die ISRs in einen exkklusiv auszuführenden Teil und einen unterbrechbaren Teil zu splitten. Man braucht dann statt dessen Hilfskrücken, die auch alles andere als umsonst sind (sowohl bezüglich der Gesamtperformance als auch bezüglich der Antwortzeiten für einen spezifischen Interrupt). Wie sowas dann aussieht und wozu es führt, kann man sich zur Genüge in den Treibermodellen der OS für die großen Systeme anschauen. Da braucht man sich dann nicht zu wundern, warum die trotz Rechenleistungen utopisch weit jenseits der eines AVR8 nicht annähernd deren garantierte Anwortzeiten erreichen können. Merke: nicht jedes Feature, was dir der sales droid anpreist, ist auch wirklich ultimativ nützlich...
c-hater schrieb: > Dann hast du aber bei echten Hardware-Interruptprioritäten > ebenfalls ein Problem. Nö, hast Du nicht. Wenn Du einen AT89LP51 mit 4 Interruptprioritäten benutzt, dann hast Du maximal 4 Instanzen laufen, ohne jeden SW-Overhead. Jede höhere Instanz kann die niederen als quasi nicht vorhanden betrachten. Das ist sehr komfortabel und sicher. Ich hab das damals schon den AVR-Entwickler Haakon Skar gefragt, warum dieser Rückschritt im Vergleich zum AT89C51. Er hat nicht verstanden, daß sowas die Programmierung erheblich erleichtert und mir hat es mehrfach Probleme bereitet.
Falk B. schrieb: > Drei, unterwegs schrieb: >> Peter D. schrieb: >>> Insbesondere da der AVR keine nested Interrupts unterstützt, >> >> Ich meine schon. Manche sogar mit Priorisierung. > > Ja, das ist der Zeitgeist. MEINEN liegt voll im Trend, so wie vegane > Ernaährung. Aber WISSEN wird mehr und mehr zur Mangelware. > > Nein, die normalen AVRs haben von Hause aus KEINE verschachtelten > (neudeutsch nested) Interrupts. Bestenfalls die ATXmegas. > Man kann sie aber per Software nachbilden, wenn man weiß was man tut. Wenn ich "meine" schreibe, dann weil ich einen höflichen Einwurf mache. Ich pöbele nicht rum, wie das andere tun. Zum Thema: ATtiny Series 0/1 (durchaus nicht das Highend von Atmel/Microchip) kennt zwei Interrupt-Prioritäten, wobei man die höhere beliebig zuweisen kann. Nesten kann man meines Wissens sowieso alle, man muss bloß das jeweilige Interrupt-Bit zurücksetzen. Sollte dies falsch sein, so bin ich für Richtigstellung dankbar, gerne ohne Blöken.
Dieter R. schrieb: > Zum Thema: ATtiny Series 0/1 (durchaus nicht das Highend von > Atmel/Microchip) Jaja, das sind erstens relativ neue und 2. relativ wenige, absierend auf dem ATXmega-Kern. Die große Masse der "normalen" AVRs ist das nicht. > kennt zwei Interrupt-Prioritäten, wobei man die höhere > beliebig zuweisen kann. Nesten kann man Soso, "nesten". https://dict.leo.org/englisch-deutsch/to%20nest > meines Wissens sowieso alle, man > muss bloß das jeweilige Interrupt-Bit zurücksetzen. Sollte dies falsch > sein, so bin ich für Richtigstellung dankbar, gerne ohne Blöken. Nein, man muss in der ISR das I-Bit mittels sei() wieder freigeben. Allerdings sollte dann die aktuelle Interruptquelle der ISR bereits gelöscht sein, sonst wird das eine Endlosschleife ;-) (z.B. In einem UART RXC Interrupt das I-Bit wieder setzen bevor man UDR gelesen hat . . .)
:
Bearbeitet durch User
Falk B. schrieb: > Allerdings sollte dann die aktuelle Interruptquelle der ISR bereits > gelöscht sein Genau das schrieb ich. Dass man außerdem Interrupts enabeln muss, damit man nesten kann, habe ich bei dem hier herrschenden Knowledgelevel mal als bekannt vorausgesetzt.
Falk B. schrieb: > Mal ne naive Frage. Sehr naiv. > Wie wäre es, basierend auf den "Tricks" mit der > Staclmessung einfach eine Testfunktion in die diversen Fuktionen > einzubauen und dort regelmäßig zu messen und im Fehlerfall bzw. wenn es > eng wird eine Debugmeldung zu erzeugen? Kostet nur ein paar Takte, > bringt aber REALE Infos mit wenig Aufwand und ohne endloses > Theoretisieren ;-) Bringt reale Infos für den "Normalfall". Zumindest solange nicht schon dieser Normalfall kritisch ist... Das hilft für die Betrachtung und den Nachweis der Sicherheit also exakt garnix. Denn dieser Nachweis besteht genau darin, auch alle möglichen Nichtnormalfälle einzuschliessen. Für sichere Software ist es zwingend nötig, auch für den worst case zu ermitteln, wieviel Speicher er verbrauchen wird. Nur so kann man sicherstellen, dass der benötigte Speicher auch im worst case tatsächlich noch verfügbar ist. Der Nachweis ist ein definitiv lösbares Problem, solange es keine Rekursionen im Code gibt. Und wie ich viel weiter oben bereits schrieb: Rekursionen kann (und sollte) man eleminieren, denn solange unbeschränkte Rekursionen existieren, ist der Code par se unsicher (und halt auch unüberprüfbar).
c-hater schrieb: > Bringt reale Infos für den "Normalfall". Das war ja auch die Absicht. > Zumindest solange nicht schon > dieser Normalfall kritisch ist... Der Op baut sicher mal KEINE Flugsteuerung mit nem ATmega328 . . . > Das hilft für die Betrachtung und den Nachweis der Sicherheit also exakt > garnix. Denn dieser Nachweis besteht genau darin, auch alle möglichen > Nichtnormalfälle einzuschliessen. Wer redet von diesem Kaliber von Software? > Für sichere Software ist es zwingend nötig, auch für den worst case zu > ermitteln, wieviel Speicher er verbrauchen wird. Nur so kann man > sicherstellen, dass der benötigte Speicher auch im worst case > tatsächlich noch verfügbar ist. Sicher, aber das ist HIER gar nicht das Thema. > Der Nachweis ist ein definitiv lösbares Problem, solange es keine > Rekursionen im Code gibt. Und wie ich viel weiter oben bereits schrieb: > Rekursionen kann (und sollte) man eleminieren, denn solange > unbeschränkte Rekursionen existieren, ist der Code par se unsicher (und > halt auch unüberprüfbar). Dann muss hochsichere Software ohne sie auskommen und der Rest (unkritische Software) im Fehlerfall eine geordnete Fehlermeldung produzieren. Aber auch Software ohne Rekursion profitiert dann von dem Ansatz.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.