[ajross]

We did. All "big" OSes have runtimes that put stacks in isolated (and very large) areas, with a guaranteed guard region at the bottom. An attack on stack bounds in Linux or Windows or OS X requires a very large depth, and will end with a regular process failure (a segfault, basically) and not a memory corruption bug.

But tools like libexpat are often used in embedded contexts, in 32 bit memory spaces, that don't have that freedom. So it's a relatively serious bug regardless.

[duped]

A fixed capacity stack isn't growable, and while the capacity is pretty big by default on desktop/server OSes is pretty big, so are stack frames so the recursion depth limit is not that big. And if user input can overflow the stack it's still a DOS.

The problem to me is that recursive functions should be a special case in the ABI, where a compiler can insert a prelude to the callsite to grow/segment the stack if needed. This is a hard problem once you have references to things on the stack, so I can understand why most ecosystems don't do it - but that doesn't mean it can't be done.

What I'm saying is that stack allocation is still dynamic memory management and in systems where its critical to avoid OOM conditions because of unbounded dynamic memory management you need code with O(1) memory complexity, and that includes the stack. A common mistake I've seen people make is assume that pushing onto the stack isn't memory allocation. It's just cheap memory allocation that can sometimes be assumed to be free, in this case and many others that's a bad assumption.

[ajross]

Fair enough, but that's getting pretty far into "research language runtimes" and not practical solutions. The tricks most people play when faced with these problems are (1) let the OS protection do it job or (2) just disallow recursion if you really can't manage that.

There's no realistic technology stack out there that does what you want.

[duped]

Go does this, as do most runtimes with stackful coroutines. Async Rust (kinda) does this where the async call stack is naturally segmented (although this doesn't get away from stack overflows in some cases because the polling call stack is not growable).

Growable stacks have been around for decades, it's far away from research language territory.

The real benefit is not to handle the worst case/OOM condition that a big enough callstack gives you. It's to make the default stack size much, much smaller for the common case where you don't need it at all (or want to shrink it later). Growable stacks use less memory on average than your typical embedded device because they can start in the dozens of bytes, instead of requiring kilo/mega bytes of stack space (allocated, not just reserved). It's kinda the only way you can make a runtime scale to millions of concurrent call stacks.

[steveklabnik]

Both Go and Rust removed segmented stacks, for the same reasons: they can really kill performance.

Go now copies stacks, and Rust only has segments if you deliberately box up a recursive call.

[duped]

Go stacks are still growable, no?

And hence the "kinda" in async Rust. While boxed futures can be thought of as a segmented stack the literal callstack is not, which can still give you a stack overflow with a bunch of nested poll() calls.

[steveklabnik]

> Go stacks are still growable, no?

Depends on what you specifically mean by "growable": when a goroutine runs out of stack space, a new one that's larger (iirc double sized) is created, the old one is copied into it, and then execution can resume.

I can see the argument both ways.

> which can still give you a stack overflow

For sure.

[BradSwain]

> while stack clashing was considered and is a theoretical possibility — denial of service was considered to be the realistic impact.

In many contexts, regular process failure is still a vulnerability.

And the stack is (usually) tiny compared to other resources. It doesn't take that many nested calls to get to the bottom of the stack. At least compared to trying to exhaust the heap or keep the CPU busy long enough to cause DoS.

[ajross]

> And the stack is (usually) tiny

This is sort of amusingly backwards. On embedded systems where I live, stacks are huge. Thread stacks of 4-16k are routinely the largest single objects the kernel sees in Zephyr. And yes, lots of RTOS apps disallow recursion (Zephyr doesn't, but does gate its use in the core system behind build-time config that can be turned off) because in that world it's hard to provide the guarantees you can get with a 64 bit mmu environment.

But if you are on a modern 64 bit OS, no: stacks are enormous. Many megabytes of mapping is routine. Obviously that's not all going to be faulted in, and most threads won't ever use more than a few kilobytes. But the region reserved for recursive use is extremely large, and unlikely to overflow except in a well-crafted deliberate attack (and even then it generally requires a few bugs in the code; most recursive algorithms are bounded by e.g. maximum tree height or something that is O(logN) and thus can't overflow).