Zulässige Verschachtelungstiefe?

Ein paar Punkte, die Dir dabei helfen könn(t)en, es selbst 
herauszufinden:

- Wie groß ist der für den Stack verfügbare Speicher?
- Wieviel Stack wird für jeden "Unterprogramm"-Aufruf verbraucht?
- Wieviel Stack belegen "Unterprogramme", wenn sie automatische 
Variablen verwenden?

Martin Lutz wrote:
> Hallo, danke für die Antwort.
> Dann muss ich also ausprobieren, d.h. das Programm im Simulator laufen
> lassen und den Stack beobachten?

Ja, ist eine Möglichkeit

> Gibt es keine andere Möglichkeiten;

Man könnte beim Programmstart den Speicher mal mit einem bestimmten
Byte fluten und nach einiger Zeit nachsehen, wieviel von diesem
'Muster' noch im Speicher vorhanden ist. Dort wo das Muster noch
existiert, ist der Speicher offenbar nicht beschrieben worden
und daher hat sich der Stack auch nicht bis dorthin ausgedehnt.

> könnte dies nicht der Compiler checken o.ä.?

Wie soll er das tun?
In dem Moment in dem ein paar Funktionsaufrufe von irgendwelchen
Bedingungen abhängen und diese wiederrum von irgendwelchen
Zuständen irgendwelcher I/O Pins, hängt der Speicherverbrauch
davon ab, was sich extern an den Anschlüssen tut. Nur: Wie
soll der Compiler wissen, was sich extern an den Anschlüssen
tut?

Das einzige was der Compiler machen kann: Bei jedem Funktions-
aufruf am Anfang der Funktion einen Check einbauen, so dass
die Funktion selbst prüft, ob der Stackpointer in Kollision
mit dem Heap kommt. Der Nachteil: Das verbaucht Resourcen,
sowohl Laufzeit als auch Programm-Speicher. Beides ist
auf einem µC sowieso meistens knapp.

Verschachtelte Aufrufe KANN der Compiler nicht prüfen, da dies ja kein 
sttischer Wert ist sondern dynamisch - währent der Ausführung - 
passiert. Ein Compiler kann nicht in die Kristallkugel schauen, wie oft 
sich ein verschaltelter Aufruf verschachtelt. Also selbst ist der µC 
Programierer, und sehen, wie viel Stack brauchst Du pro Aufruf, wieviele 
lokale Variablen benötigst Du dabei. Dem ganzen ziehst Du den Platz der 
globalen Variablen ab (die liegen an den unteren Adressen des RAM). 
Daraus kannst Du Dir die benötigte Speichergrösse ableiten. Achtung, am 
besten siehst Du Dir des ASM-Code an, der Controller pusht auch gerne 
Register auf den Stack, bevor er die Subroutine ausführt. Jedenfalls 
kommt die Returnadresse auf den Stack.

1

avr-objdump -g myProject.elf

 liefert sehr brauchbare Angaben.

Viel Spass beim Zählen ist eine eher langweilige Aufgabe. Kann der 
Simulator den Du verwendest Stackframes und Variablen im Speicher 
anzeigen?

Gabriel Wegscheider wrote:
> Verschachtelte Aufrufe KANN der Compiler nicht prüfen, da dies ja kein
> sttischer Wert ist sondern dynamisch - währent der Ausführung -
> passiert. Ein Compiler kann nicht in die Kristallkugel schauen, wie oft
> sich ein verschaltelter Aufruf verschachtelt.

Das könnte der Compiler sehr wohl tun, wenn man davon ausgeht, daß alle 
Bedingungen wahr sind und keine Rekursion erfolgt.

Der Keil C51 macht das auch, um den SRAM überlagern zu können.

Rekursionen sollte man auf nem MC generell meiden, da sie exzessiven 
SRAM- und CPU-Zeit-Verbrauch bewirken.


Ich schreibe gerne viele kleine Funktionen (ab 5-Zeiler) und hatte noch 
nie Probleme wegen der Schachtelungstiefe.

Vielleicht beim ATtiny13 könnte es knapp werden (64 Byte SRAM), aber da 
geht eher der Flash aus (512 Words).


Peter

Irgendwo hier flog mal ein Stück Code rum, das den Stackverbrauch 
"nachmessen" kann:

in einer der .init-Sections wird der Speicher mit nem Wert 
überschrieben, und später kann man nachzählen wieviel vom Speicher noch 
diesen Wert hat, also wie tief der Stack in der Zwischenzeit gewachsen 
ist.


mem-check.h:

1

#ifndef _MEM_CHECK_H_

2

#define _MEM_CHECK_H_

3

4

extern unsigned short get_mem_unused (void);

5

6

#endif  /* _MEM_CHECK_H_ */

mem-check.c:

1

#include <avr/io.h>  // RAMEND

2

#include "mem-check.h"

3

4

// Mask to init SRAM and check against

5

#define MASK 0xaa

6

7

// From linker script

8

extern unsigned char __heap_start;

9

10

unsigned short

11

get_mem_unused (void)

12

{

13

   unsigned short unused = 0;

14

   unsigned char *p = &__heap_start;

15

16

   do

17

   {

18

      if (*p++ != MASK)

19

         break;

20

21

      unused++;

22

   } while (p <= (unsigned char*) RAMEND);

23

24

      return unused;

25

}

26

27

/* !!! never call this function !!! */

28

void __attribute__ ((naked, section (".init8")))

29

__init8_mem (void)

30

{

31

   __asm volatile (

32

      "ldi r30, lo8 (__heap_start)"  "\n\t"

33

      "ldi r31, hi8 (__heap_start)"  "\n\t"

34

      "ldi r24, %0"                  "\n\t"

35

      "ldi r25, hi8 (%1)"            "\n"

36

      "0:"                           "\n\t"

37

      "st  Z+,  r24"                 "\n\t"

38

      "cpi r30, lo8 (%1)"            "\n\t"

39

      "cpc r31, r25"                 "\n\t"

40

      "brlo 0b"

41

         :

42

         : "i" (MASK), "i" (RAMEND+1)

43

   );

44

}

Peter Dannegger wrote:
>Das könnte der Compiler sehr wohl tun, wenn man davon ausgeht, daß alle
>Bedingungen wahr sind und keine Rekursion erfolgt.
>
>Der Keil C51 macht das auch, um den SRAM überlagern zu können.
>
>Rekursionen sollte man auf nem MC generell meiden, da sie exzessiven
>SRAM- und CPU-Zeit-Verbrauch bewirken.
Das ist aber eigentlich nicht die Aufgabe des Compilers, schön wenn 
dieser Compiler das kann.

Matthias wrote:
> Bei einem so kleinen Controller würde ich keine "lokalen" Variablen
> empfehlen. Dann gibt einem der Compiler gleich eine Übersicht, über
> den verbrauch an RAM (glaub .bss ?). Ausserdem meckert er in jedem Fall,
> wenn  der Speicher ausgeht.
Gerade bei einem kleinen Controller sind lokale Variblan sinnvoll, das 
hier der Speicher mehrfach genutzt wird. Die lokalen Variablen werden 
auf dem Stack angelegt und der verwendete Speicher ist dannach wieder 
frei. Globale Variablen hingegen belegen den Speicher von Anfang an und 
schliessen die Möglichkeit aus, einen Speicherbereich merhrfach zu 
verwenden.

> Das kann man dann nutzen, um die Größe des restlichen RAMs zu ermitteln:
>
> Array anlegen und die Größe solange erhöhen bis eine Fehlermeldung
> kommt.
> Die Größe, bevor die Fehlermeldung kommt, ist dann der noch freie
> Speicher.
>
> Dann hängt es letztlich von der Anzahl der Funktionen ab, die
> verschachtelt aufgerufen werden.
> Ein AVR braucht 2 bzw. 3 Byte pro Funktionsaufruf, um die
> Rückspringadresse zu sichern. Der Compiler wird dann wahrscheinlich noch
> ein paar Register sichern, die innerhalb der Funktion benutzt werden.
>
Und mit den globalen Variablen hast Du noch lange nicht den 
Speicherverbrauch abgedecht. Bei jedem Funktionsaufruf werden die 
Parameter, die Rücksprungadresse und "ganz nach Lust und Laune" des 
Compilers Register abgelegt (push)

> Hat man nur globale Variablen, sollte das hoffentlich recht wenig sein.
> Kann man allerdings im Assemblercode prüfen.
>
> Bei kleinen Controllern kann man sich die Verschachtelung meistens an
> einer Hand abzählen. Dazu rechnet man dann noch einen ISR Aufruf dazu.
>
> Weiss jeman, wie man die Anzahl der vom Compiler gesicherten Register
> bei einem Funktionsaufruf abschätzen / bestimmen kann? (ausser im
> Assemblercode zu schauen)?
Nein kann man nicht einheitlich sagen. Ich hab in einem kleine Projekt 
gerade Stackframes-Sizes zwischen 4 und 18 Bytes gemessen.
Die Grösse der Stackframes ist sehr unterschiedlich, lässt jedoch für 
jede Funktion auch ausrechnen.

1

avr-objdump -g myProject.elf

liefert alle Daten, "ein paar regexp mit etwas logik" darüberlaufen und 
man kann einen Report generieren:

1

StackFrame: 'global' from 0xFFFFFFFF to 0x0 PushCount 0 FrameSize 8388719

2

    Var   'PID_Param.Kp   ' of 'int16_t             ' @ 0x800068

3

    Var   'PID_Param.Ki   ' of 'int16_t             ' @ 0x80006A

4

    Var   'PID_Param.Kd   ' of 'int16_t             ' @ 0x80006C

5

    Var   'PID_Param.Ta   ' of 'int16_t             ' @ 0x80006E

6

    Var   'DEBUG          ' of 'int16_t             ' @ 0x800064

7

    Var   'uDEBUG         ' of 'uint16_t            ' @ 0x800066

8

    Var   'sum            ' of 'int16_t             ' @ 0x800062

9

    Var   'last_error     ' of 'int16_t             ' @ 0x800060

10

StackFrame: '__vectors' from 0x0 to 0x26 PushCount 0 FrameSize 0

11

StackFrame: '__bad_interrupt' from 0x5A to 0x5C PushCount 0 FrameSize 0

12

StackFrame: 'main' from 0x5C to 0xB8 PushCount 0 FrameSize 8

13

    Var   'result         ' of 'unsigned_int        ' @ 0x3

14

    Var   'ref            ' of 'unsigned_int        ' @ 0x5

15

    Var   'sens           ' of 'unsigned_int        ' @ 0x7

16

    Var   'x              ' of 'unsigned_int        ' @ 0x1

17

StackFrame: 'PIDcontroller_init' from 0xB8 to 0x102 PushCount 2 FrameSize 4

18

    Var   'reference      ' of 'int16_t             ' @ 0x1

19

    Var   'process        ' of 'int16_t             ' @ 0x3

20

StackFrame: 'multULimit' from 0x102 to 0x164 PushCount 2 FrameSize 6

21

    Var   'a              ' of 'uint16_t            ' @ 0x3

22

    Var   'b              ' of 'uint16_t            ' @ 0x5

23

    Var   'result         ' of 'uint16_t            ' @ 0x1

24

StackFrame: 'multSULimit' from 0x164 to 0x244 PushCount 6 FrameSize 8

25

    Var   'a              ' of 'int16_t             ' @ 0x5

26

    Var   'b              ' of 'uint16_t            ' @ 0x7

27

    Var   'result         ' of 'int32_t             ' @ 0x1

28

StackFrame: 'PIDcontrollerUnsigned_schedule' from 0x244 to 0x412 PushCount 2 FrameSize 18

29

    Var   'reference      ' of 'int16_t             ' @ 0xF

30

    Var   'process        ' of 'int16_t             ' @ 0x11

31

    Var   'result         ' of 'int32_t             ' @ 0x1

32

    Var   'DPart          ' of 'uint16_t            ' @ 0x5

33

    Var   'IPart          ' of 'uint16_t            ' @ 0x7

34

    Var   'tmp            ' of 'uint16_t            ' @ 0x9

35

    Var   'PPart          ' of 'uint16_t            ' @ 0xB

36

    Var   'error          ' of 'int16_t             ' @ 0xD

Sobald dann inline asm drinnen ist, macht mein Analyscode derzeit eine 
Bauchlandung.... Da liefert nähmlich avr-objdump keine sinnvollen 
Ergebnisse mehr   :(

Matthias wrote:

> Bei einem so kleinen Controller würde ich keine "lokalen" Variablen
> empfehlen.

Im Gegenteil. Ein AVR hat recht viele Register und die meisten 
Funktionen kommen deshalb ausschliesslich mit Registern aus, müssen also 
dafür keinen Speicher adressieren. Das kommt dem Code sehr zugute.

Was hingegen tatsählich sinnvoll sein kann: nicht-skalare Variablen 
(arrays, structs) und Variablen deren Adresse verwendet wird als static 
zu deklarieren. Denn solche Variablen landen sonst unweigerlich auf dem 
Stack, und AVR kann damit zwar besser umgehen als etliche anderen 
8-Bitter, aber immer noch schlechter als mit direkt adressierten. 
Ausserdem ist die Verwaltung eines Stackframe beim GCC u.U. recht 
aufwendig, wird aber nur nötig wenn solche Variablen überhaupt 
existieren.

> Dann gibt einem der Compiler gleich eine Übersicht,

Inwieweit das ein Vorteil ist hängt auch vom Compiler ab. Auf 
Microcontroller wie 8051 und PIC spezialisierte Compiler pflegen das 
Program draufhin zu untersuchen, welche Variablen übereinander gelegt 
werden können. GCC tut das aufgrund völlig anderer Herkunft nicht. Daher 
sorgen statisch angelegte Variablen beim GCC für deutlich höheren 
RAM-Verbrauch als lokale Variablen.

Zudem leidet der Code massiv, wenn skalare Daten statisch angelegt 
werden, so dass nebem dem RAM auch noch das ROM knapp werden kann.

Gabriel Wegscheider wrote:

> liefert alle Daten, "ein paar regexp mit etwas logik" darüberlaufen und
> man kann einen Report generieren:

Wobei man da ein bischen was draufrechnen muss. Seht dort 0, kommen noch 
2-3 Bytes für die Return-Adresse dazu. Bei > 0 muss man darüber hinaus 2 
Bytes für den Frame-Pointer hinzurechnen.

Hier mal eine Funktion, mit der man den Stackverbrauch zur Laufzeit 
ermitteln kann.
Funktioniert allerdings nur, wenn kein malloc benutzt wird.

1

#define FREE_MARK 0x77

2

3

extern u8 __bss_end;                    // lowest stack address

4

5

extern u8 __stack;                      // highest stack address

6

7

8

u16 stack_size( void )                  // available stack

9

{

10

  return (u16)&__stack - (u16)&__bss_end + 1;

11

}

12

13

14

u16 stack_free( void )                  // unused stack after last call

15

{

16

  u8 flag = 1;

17

  u16 i, free = 0;

18

  u8 * mp = &__bss_end;

19

20

  for( i = SP - (u16)&__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

}

Peter

Andreas Kaiser wrote:
>> liefert alle Daten, "ein paar regexp mit etwas logik" darüberlaufen und
>> man kann einen Report generieren:
> Wobei man da ein bischen was draufrechnen muss. Seht dort 0, kommen noch
> 2-3 Bytes für die Return-Adresse dazu. Bei > 0 muss man darüber hinaus 2
> Bytes für den Frame-Pointer hinzurechnen.
Hier nicht!
Es steht 0 dort, wenn der Stackframe (oder pseudo-Stackframe) 0 ist. die 
Sektion __vectors ist die Jumptable am Anfang des Programmspeichers, die 
hat KEINEN Frame, daher 0 Byte Framesize. "global" ist auch kein echter 
Frame, hab ihm aber in der Datenstruktur Frames reingepackt. Daher hat 
"global" auch eine Size von -1.
Die Returnadresse, Returnparameter und Funktiuonsparameter hab ich bei 
diesen Berechnungen bereits berücksichtigt. Der PushCount wird aus 
"avr-objdump -d" extrahiert.
Soweit ich das im Simulator verifiziert habe stimmen diese Frameangaben 
(sonst hätt ich sie ja korrigiert... :)  )
... das mit "ein paar regexp und etwas logik" wahr etwas salopp 
formuliert, das Parsen der avr-objdumps entspricht ~ 300 LOC (CPP mit 
vielen RegExp). Die Strukturen noch nicht eingerechnet.

@Peter:

Da gefällt mir die Version die ich weiter oben gepostet hab aber besser.
Die kann man einfach irgendwo, z.B. in der main-schleife, aufrufen und 
das Ergebnis ausgeben, und hat dort den Peak-Wert des Stackverbrauchs, 
inkl. IRQs die seit Programmstart aufgerufen wurden.

Ernst Bachmann wrote:
> @Peter:
>
> Da gefällt mir die Version die ich weiter oben gepostet hab aber besser.
> Die kann man einfach irgendwo, z.B. in der main-schleife, aufrufen und
> das Ergebnis ausgeben, und hat dort den Peak-Wert des Stackverbrauchs,
> inkl. IRQs die seit Programmstart aufgerufen wurden.

Ich wüßte jetzt nicht, wo meine Funktion Beschränkungen bezüglich der 
Aufrufbarkeit hätte.


Man ruft sie einmal am Anfang des main auf, damit sie den ungenutzten 
Bereich mit dem Muster füllt.
Und dann an beliebiger anderer Stelle, um den Verbrauch, seit dem 
letzten Aufruf zu ermitteln.

Das ist ganz praktisch. Man kann damit eine Sequenz klammern, die man 
als Speicherfresser in Verdacht hat und prüfen.

Man kann sie also beliebig und mehrmals aufrufen.


Ich versuche möglichst kein Assembler zu nehmen, wenns auch in C geht.


Peter

@Peter:

Ups, stimmt...
Hab ganz übersehen das die Schleife sozusagen den freien Speicher für 
den nächsten Aufruf vorbereitet, und bin wg. dem Schleifenende bei "SP" 
davon ausgegangen dass er nur den aktuellen Stack-Füllstand 
betrachtet...

Nehme also alles zurück und behaupte das Gegenteil, schöne Funktion und 
spart das Herumgefummel in den .init-Sections.