Protecting against stack overflow/underflow

Discussion of hardware and software development for Super NES and Super Famicom. See the SNESdev wiki for more information.

Moderator: Moderators

Forum rules
  • For making cartridges of your Super NES games, see Reproduction.
User avatar
jeffythedragonslayer
Posts: 344
Joined: Thu Dec 09, 2021 12:29 pm

Protecting against stack overflow/underflow

Post by jeffythedragonslayer »

I think a stack overflow/underflow warning would be a good feature for game dev focused emulators - I figured out the answer to some questions while writing this up but I think there are still some unsolved problems.

The CPU will try to push to a full stack or pull from an empty stack if you tell it to, not caring that it is trashing things. Sometimes it is easy to tell where the stack begins - you look for a TCS command. For example, this is the beginning of Seiken Densetsu 3, where we see the stack pointer being initialized to $00FF:

Code: Select all

FF00   CLC                      
FF01   XCE                      
FF02   REP #$10                 
FF04   REP #$20                 
FF06   LDA #$00FF               
FF09   TCS
But the stack is a circular buffer, so (on the 6502) you can initialize the stack pointer to anywhere on page one (or even not initialize it at all!) and everything will still be just fine, even through the push and pull that causes the stack pointer to wraparound between $100 and $1FF. The CPU doesn't care.

Is anyone aware of any SNES games that do not initialize the stack pointer? Is it known whether its value is stable on reset? Whatever it may happen to be, I think the emulator can consider the SP having that value an "empty" stack to protect against stack underflow, but protecting against stack overflows seems more difficult:

As we know that the stack grows towards zero, it appears to be allocated in page zero in SD3. That's easier to see here; it's the 00 in $00FF. On the 65816 the stack pointer need not be confined to page one like the 6502, but it is confined to bank zero. But bank zero is also where non-stack things like hardware vectors live, so a stack overflow warning when the stack pointer becomes equal to its initial value again seems very late in the game; something likely to protect against recursive functions gone haywire, but not much else. What else can be done to figure out where non-stack things live? Look for RTI? That generally tells you where the NMI handler ends. What about where it begins, look in the source code for where the VECTOR segment is? That has the address for where all of the COP, BRK, ABT, NMI, RST, IRQ handlers live, but feels like a kludge. I can't really think of an easy way to implement this.
Last edited by jeffythedragonslayer on Mon Aug 22, 2022 11:58 am, edited 1 time in total.
User avatar
Dwedit
Posts: 4924
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Protecting against stack overflow/underflow

Post by Dwedit »

If all memory access to the stack area is done by stack instructions alone, then a stack overflow can become unnoticed, and even be completely harmless.

One NES homebrew game (a rather tasteless game involving terrorism) happens to eventually crash due to a stack overflow bug, but it only crashes because parts of the stack page are overwritten elsewhere.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
User avatar
jeffythedragonslayer
Posts: 344
Joined: Thu Dec 09, 2021 12:29 pm

Re: Protecting against stack overflow/underflow

Post by jeffythedragonslayer »

Dwedit wrote: Mon Aug 22, 2022 11:55 am If all memory access to the stack area is done by stack instructions alone, then a stack overflow can become unnoticed, and even be completely harmless.
Is this the same thing as the wraparound situation I mentioned? I'm not really considering that an overflow - one of the situations I hope to get early warning against is when a value is pushed to the stack that overwrites the very first value that was pushed (assuming all memory access to the stack were by stack instructions like you said).
Fiskbit
Posts: 891
Joined: Sat Nov 18, 2017 9:15 pm

Re: Protecting against stack overflow/underflow

Post by Fiskbit »

Use a stack canary, a variable at the bounds of the stack. If it changes unexpectedly, it can be assumed the stack has overflowed. If you want to make it less likely the value of the stack canary happens to match the value pushed, you could make its value change every frame, perhaps by setting it to the value of your frame counter.
turboxray
Posts: 348
Joined: Thu Oct 31, 2019 12:56 am

Re: Protecting against stack overflow/underflow

Post by turboxray »

jeffythedragonslayer wrote: Mon Aug 22, 2022 11:16 am I think a stack overflow/underflow warning would be a good feature for game dev focused emulators - I figured out the answer to some questions while writing this up but I think there are still some unsolved problems.

The CPU will try to push to a full stack or pull from an empty stack if you tell it to, not caring that it is trashing things. Sometimes it is easy to tell where the stack begins - you look for a TCS command. For example, this is the beginning of Seiken Densetsu 3, where we see the stack pointer being initialized to $00FF:

Code: Select all

FF00   CLC                      
FF01   XCE                      
FF02   REP #$10                 
FF04   REP #$20                 
FF06   LDA #$00FF               
FF09   TCS
But the stack is a circular buffer, so (on the 6502) you can initialize the stack pointer to anywhere on page one (or even not initialize it at all!) and everything will still be just fine, even through the push and pull that causes the stack pointer to wraparound between $100 and $1FF. The CPU doesn't care.

Is anyone aware of any SNES games that do not initialize the stack pointer? Is it known whether its value is stable on reset? Whatever it may happen to be, I think the emulator can consider the SP having that value an "empty" stack to protect against stack underflow, but protecting against stack overflows seems more difficult:

As we know that the stack grows towards zero, it appears to be allocated in page zero in SD3. That's easier to see here; it's the 00 in $00FF. On the 65816 the stack pointer need not be confined to page one like the 6502, but it is confined to bank zero. But bank zero is also where non-stack things like hardware vectors live, so a stack overflow warning when the stack pointer becomes equal to its initial value again seems very late in the game; something likely to protect against recursive functions gone haywire, but not much else. What else can be done to figure out where non-stack things live? Look for RTI? That generally tells you where the NMI handler ends. What about where it begins, look in the source code for where the VECTOR segment is? That has the address for where all of the COP, BRK, ABT, NMI, RST, IRQ handlers live, but feels like a kludge. I can't really think of an easy way to implement this.
Are you really looking for a run-time monitoring/check method for every stack access??? I can see maybe having an emulator check this (for an overflow or canary overwrite), but seems a little extreme for run-time on an old processor.
creaothceann
Posts: 611
Joined: Mon Jan 23, 2006 7:47 am
Location: Germany
Contact:

Re: Protecting against stack overflow/underflow

Post by creaothceann »

jeffythedragonslayer wrote: Mon Aug 22, 2022 11:16 am Is it known whether its value is stable on reset?
On RESET the CPU switches back to 6502 mode, which is detailed here.
My current setup:
Super Famicom ("2/1/3" SNS-CPU-GPM-02) → SCART → OSSC → StarTech USB3HDCAP → AmaRecTV 3.10
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Protecting against stack overflow/underflow

Post by rainwarrior »

What Fiskbit said, but also in an emulator you can put a breakpoint on writes/reads to your reserved bytes at the ends of the stack. For the purposes of having a breakpoint, the value of the "canary" won't matter... I think that's only for runtime checking? Though a lot of stack problems probably wouldn't make it back to the code that checks the canary.

In homebrew, having a reserved byte at the start and end of the range gives you a way to detect both underflow and overflow reliably.

If trying to diagnose existing games, you might temporarily patch the game to start its stack one byte lower (or just add a push at the start) for the underflow byte. You'll have to manually deduce where the overflow point is. This assumes there are 2 bytes free in the program's reserved stack area, but it's usually unlikely for a program to use all of its stack space... generally you only "almost" fill it up when you're in the process of getting to an overflow.

On NES it's a little easier because it wraps at a fixed 256 byte page, and many games don't try to store anything else on the stack. Most games initialize the stack

On SNES I think you pretty much have to initialize the stack to get a working program? I'm not aware of any games that don't. I believe reset switches to emulation mode, which loads the high byte of the stack pointer with $01 but the low byte is uninitialized. Unless you leave emulation mode on (do any SNES games do anything with emulation mode?) it'd be liable to encroach on the zero page... maybe if you wanted to reserve both $00 and $01 for the stack and didn't care that it was up to 50% wasted, it would be safe to leave uninitialized?
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Protecting against stack overflow/underflow

Post by rainwarrior »

creaothceann wrote: Mon Aug 22, 2022 12:50 pmOn RESET the CPU switches back to 6502 mode, which is detailed here.
That page doesn't adequately cover it. It talks about SP starting at $00 in Visual6502 but the 6502 itself does not initialize SP. For the 65C816 reset always enables emulation mode, which does initalize the high byte of SP (non-existant on 6502) to $01, but leaves the low byte uninitialized. The 65C816 datasheet covers this in section 2.25 Reset.
Pokun
Posts: 2681
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Protecting against stack overflow/underflow

Post by Pokun »

I thought the RESET interrupt worked exactly like every other interrupt which includes pushing both PC and P to the stack. But since neither PC, P, SP nor RAM are initialized on boot, that normally doesn't mean much to the programmer (unless non-volatile RAM is used).
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Protecting against stack overflow/underflow

Post by rainwarrior »

I believe RESET doesn't actually modify RAM. It pretends to use the stack, reusing part of the interrupt operation, but doesn't actually write to it. The consequence is that SP moves, but since its value is uninitialized (or usually unknown at the point of reset) it doesn't matter much.
Pokun
Posts: 2681
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Protecting against stack overflow/underflow

Post by Pokun »

Ah I see, that makes sense, so RESET works like a normal interrupt except that RAM writes blocked during the RESET preventing it from overwriting something important in case non-volatile RAM is actually used on page 1. The above link doesn't seem to describe the RESET process too accurately.
User avatar
jeffythedragonslayer
Posts: 344
Joined: Thu Dec 09, 2021 12:29 pm

Re: Protecting against stack overflow/underflow

Post by jeffythedragonslayer »

rainwarrior wrote: Mon Aug 22, 2022 1:07 pm On SNES I think you pretty much have to initialize the stack to get a working program?
I was able to get away with not initializing the stack pointer on the SNES for quite a long time (sprites and backgrounds displayed). What made me initialize it wasn't that anything was broken, but when I would do a Squaresoft-style soft reset, the old stack data from before doing L+R+Start+Select would still be there, which I found confusing.
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Protecting against stack overflow/underflow

Post by rainwarrior »

Ah, well if you've got free space on $00 and your stack isn't going too deep, I guess it won't cause a problem, though having S able to be as low as $100 and as high as $1FF could make for some tricky to diagnose intermittent or hardware-only errors if it ever does overlap important things on the zero page.

At any rate, there isn't really any good reason not to initialize it. Even on NES it's a pretty good idea... though because it wraps to its own page it's a lot safer in the case that you don't.
User avatar
jeffythedragonslayer
Posts: 344
Joined: Thu Dec 09, 2021 12:29 pm

Re: Protecting against stack overflow/underflow

Post by jeffythedragonslayer »

turboxray wrote: Mon Aug 22, 2022 12:36 pmAre you really looking for a run-time monitoring/check method for every stack access??? I can see maybe having an emulator check this (for an overflow or canary overwrite), but seems a little extreme for run-time on an old processor.
Yeah; I conditionally disable the debugging stuff when I want to do a release build. I don't really care about performance until my code isn't broken anymore - the point of this warning is to make it easier to tell when you're trashing the stack. I don't know of an easy way to probe the program counter on real hardware - emulation is definitely easier to debug in.

A canary, in the form of a write breakpoint, is a good solution if you're developing the game and know how much stack space you've allocated, but I'm brainstorming a more general solution where the emulator can figure out where the stack begins and ends.
turboxray
Posts: 348
Joined: Thu Oct 31, 2019 12:56 am

Re: Protecting against stack overflow/underflow

Post by turboxray »

jeffythedragonslayer wrote: Mon Aug 22, 2022 3:41 pm
turboxray wrote: Mon Aug 22, 2022 12:36 pmAre you really looking for a run-time monitoring/check method for every stack access??? I can see maybe having an emulator check this (for an overflow or canary overwrite), but seems a little extreme for run-time on an old processor.
Yeah; I conditionally disable the debugging stuff when I want to do a release build. I don't really care about performance until my code isn't broken anymore - the point of this warning is to make it easier to tell when you're trashing the stack. I don't know of an easy way to probe the program counter on real hardware - emulation is definitely easier to debug in.

A canary, in the form of a write breakpoint, is a good solution if you're developing the game and know how much stack space you've allocated, but I'm brainstorming a more general solution where the emulator can figure out where the stack begins and ends.
Some sort of hardware implementation on the real system would be great - that way you don't need to incur performance penalty from a software solution (i.e. timing will be the same in "debugging" as in non-debugging mode). I assume you can generate interrupts from the cart? So some sort of intermediate device that monitors all read/write access to specific memory ranges (traps) - and generates an interrupt. More trivial on an emulator but would definitely be nice to have on a real system development.
Post Reply