Excessive stack overflow

[divB (Gast)]

Hi,

Auf einem ATmega163 implementiere ich AES. Ich habe nun das Problem dass 
ich relativ reproduzierbar in der 8. Runde folgende Meldung erhalte:

    AVR Simulator: Excessive stack overflow, stop sim.

Das kranke dabei: Ich verwende keine einzige Rekursion, wenig Variablen 
auf dem Stack und eine relativ geringe Verschachtelungstiefe.

Die Hauptschleife sieht so aus:

for(round = 1; round < 16; round++)
{
  SubBytes(state);
  ShiftRows(state);
  MixColumns(state);
  GenerateNextKey(ext_key);
  AddRoundKey(state, ext_key);
}

AddRoundKey beinhaltet nur eine simple Vorschleife mit XOR-Befehlen

ShiftRows macht lediglich ein paar Swaps mit XOR

SubBytes hat ebenfalls nur EINE for-Schleife

GenerateNextKey beinhaltet eine 10-zeilige Schleife mit 2 if-Abfragen 
und definiert ebenfalls nur 2 Variablen.

Lediglich MixColumns ist ein bisschen größer, hat eber ebenfalls nur 
eine for-Schleife und definiert ein "unsigned char col[4]". Weiters wird 
einige Male (aber immer auf gleichem Level) eine Funktion gf8mul 
aufgerufen. gf8mul definiert exakt 3 unsigned chars und hat sagenhaft 
riesige 6 Zeilen.

Ja, wirklich, es kommt nichts vor dass "exzessiv" den Stack auffressen 
könnte. Vor allem: Was ich dabei nicht verstehe: Nachdem in der Schleife 
ja immer das gleiche gemacht wird und alles auf einer Ebene ist, kann 
der Stack dadurch ja nicht größer werden! Wieso kommt dann erst bei der 
8-ten Runde der Stack Overflow?

Irgendwie bin ich mit meinem Latein völlig am Ende, leider fehlt mir 
auch die Kenntnis wie ich den Stack überprüfen kann...

Wie groß ist dieser überhaupt?

lg
divB

[Sven P. (Gast)]

Zeig bitte den Rest vom Quelltext, sonst wird das nix.

[Gast (Gast)]

Der Stapel ist durch die SRAM größe begrenzt da es der ort ist
wo alles hingeschaufelt wird.

[Marcus M. (marcus67)]

Wenn Du keinen Speicher auf dem Stack verbrauchst wird es wohl daran 
liegen, daß Du mit einem kaputten Pointer irgendwas überschreibst was 
sonst noch gebraucht wird (Stack, Rücksprungadressen etc.). Das kann zu 
allen denkbaren Effekten führen.

Ist leider sehr schwer zu finden, da es meist erst später an anderer 
Stelle kracht ...

Gruß, Marcus

[Karl H. (kbuchegg)]

Da du das Ganze ja im Simulator laufen hast, kannst du doch einfach mal 
den Stackpointer im Registerfenster beobachten. Schreib dir in einem 
Schleifendurchlauf die Werte auf.
Der Wert vor einem Funktionsaufruf muss identisch sein zum Wert, den du 
nach dem Funktionsaufruf siehst. Auch muessen die Werte vor den 
Funktionsaufrufen in jedem Durchlauf durch die Hauptschleife identisch 
sein.

Auf die Art müsstest du sehr schnell rausfinden in welcher Funktion du 
den Stack zerschiesst.

Auch die Beobachtung des Programcounters ist oft hilfreich, zeigt sie 
doch zuverlässig einen zerschossene Rücksprungadresse auf dem Stack an.

Abgesehen davon:
1) Deine Hauptschleife ist offensichtlich in Ordnung.
2) Deine Funktionen sind deiner Meinung nach auch in Ordnung.

Na dann ist ja alles klar! Dann dürfte es kein Problem geben. Da es aber 
ein Problem gibt, muss eine der beiden Aussagen da oben falsch sein. 
Rate mal welche?

Zu deiner Beruhigung: Es kommt zwar vor, dass Compiler Fehler enthalten, 
die sind aber meistens in eher 'esoterischen' Bereichen zu finden und 
manifestieren sich nicht so offensichtlich. Wenn Probleme auftauche, 
dann ist die Wahrscheinlichkeit, dass du irgendwo einen Fehler gemacht 
hast um ein Vielfaches höher, als daß der Compiler Mist gemacht hat.

[divB (Gast)]

Hi,

Also den Fehler hab ich jetzt glaub ich gefunden. Gaanz am Anfang werden 
jeweils 2 Strukturen definiert die gemeinsam um die 450 Bytes groß sind. 
Da kann ich mir schon vorstellen dass der Stack dann irgendwann 
überläuft.

Die große Frage aber nun: Wie groß ist der Stack beim AVR bzw. 
ATmega163? Lässt sich das auch einstellen?

Und weiters: Wird dieser Speicher reserviert? Angenommen meine Mem 
sieht so aus:

AVR Memory Usage
----------------
Device: atmega163

Program:   17424 bytes (106.3% Full)
(.text + .data + .bootloader)

Data:        957 bytes (93.5% Full)
(.data + .bss + .noinit)

(das ich hier noch Probleme mit dem Programmcode hab ich klar)...heisst 
dass das der Stack bei den 93.5% schon dabei sind oder nicht?

lg
divB

[Klaus (Gast)]

Nein, das sind nur die statischen/globalen Variablen.

Der Stack, also Rücksprungadressen und alle lokalen Variablen sind da 
nicht mitgezählt.


Der Speicher für den Stack wird nicht reserviert. Der Stack wächst 
einfach von oben nach unten. Während die globalen Variablen im unteren 
Bereich des RAMs liegen. Wenn der Stack nun immer größer wird, wächst 
der irgendwann einfach in deine Variablen rein, und überschreibt da was 
und es gibt wilde Fehler. Du muss immer im Hinterkopf behalten, dass ja 
kein Betriebssystem in Hintergrund da ist, was auf deine 
Speicherzugriffe aufpassen kann. Deshalb gibts auch kein reservierten 
Speicherbereich für den Stack.

[divB (Gast)]

Ok, das erklärt natürlich wieso meine Tabellen alle falsche Werte 
hatten/überschrieben wurden. Aber: Wenn der Stack einfach wächst, wie 
stellt dann der Simulator einen Overflow fest?!

Wie kann ich am besten abschätzen wieviel Platz ich für den Stack 
freilassen soll?

* Pro Funktionsaufruf: 2 Byte Rücksprung + Parameter
* Alle on-the-fly definierten Variablen

?

lg
divB

[Klaus (Gast)]

> Ok, das erklärt natürlich wieso meine Tabellen alle falsche Werte
> hatten/überschrieben wurden. Aber: Wenn der Stack einfach wächst, wie
> stellt dann der Simulator einen Overflow fest?!

Der Simulator kennt ja die Position deiner Variablen und er kennt den 
Stackpointer. Also kann er auch einen Stack Overflow überprüfen. Der 
Simulator macht hier praktischerweise also mehr, als nur die reine 
Hardware zu simulieren.

>Wie kann ich am besten abschätzen wieviel Platz ich für den Stack
>freilassen soll?
>
>* Pro Funktionsaufruf: 2 Byte Rücksprung + Parameter
>* Alle on-the-fly definierten Variablen

Ja, so in etwa musst du das abschätzen.