Hacker News Reader

Comment by QuadrupleA | Hacker News Reader

Never thought about it but yes, what a huge (and easily implementable) oversight - stackSize(), stackUsed(), stackTopPtr() would be a few asm instructions in most cases.

View on HN

There is no useful way to employ these functions. It's equivalent to asking if a mutex is locked. That piece of information is worthless.

If writing a recursive algorithm on arbitrary input, check remaining stack size upon recursive function entry. If space is depleted, allocate a new fiber (aka a brand new clean stack), switch to it, and resume. Switch back to calling fiber on stack unwind.

If you’re writing a recursive algorithm on arbitrary input, you should be using a stack container to store your state, not the call stack.

you mean std::stack?

Why do you think so? A stack container ordinarily contains a single data type. You can jump through some hoops to let it store completely arbitrary types, but when you consider a function's stack frame as a distinct type, the call stack naturally does that for you.

Most commonly you handle this with a stack of records.

1. A stack frame usually takes up far more memory than the state that actually needs to be persisted, due to local variables and padding from alignment requirements. With a stack container, you can specify exactly what gets stored, and save on your memory footprint.

2. There are very few knobs you can tweak to control how your call stack space is allocated or represented in memory. With a stack container, you have much finer control over that - you can do reallocations or define custom error handling when you overflow the container, you can deallocate/shrink the container when you no longer need the space, you can serialize the container to disk to make your processing resumable, etc.

3. A call stack has a very limited set of operations. You can only access data from the current stack frame, and you can only push/pop (call/return) stack frames. But with your own stack-like data structure, you could extend it to do far more, e.g. accessing data from the first or last n traversals, or insert/remove multiple elements at once.

Could you explain this please?

Just like with the mutex, this piece of information is out of date as soon as it reaches you. Preparations for whatever action you perform after, or the very act of retrieving this information may invalidate it.

"I can't complete this recursive algorithm because I ran out of stack at this particular step" is a much nicer error message than "segmentation fault". For that it would be useful if you could check remaining stack space before recursing.

Whatever values these functions returned, there would be no way for you to make a determination on whether another step can be performed.

I could see that sort of thing being very useful for a debugger.

Debuggers don't need to restrict themselves to what the C standard provides, and never do.

What are you talking about? For lots of functions, it is perfectly possible to statically determine a maximum stack size (not all functions obviously, that would be the halting problem). An trivial example would be a function that calls no other functions, but you can imagine others: functions with static call trees (i.e. no function pointers), don’t use VLAs or alloca, and that are not recursive (mutually, indirectly, or otherwise) will have a static limit on possible stack usage.

If you’ve formally verified that function X uses at most Y pages of stack, and the remaining stack is smaller than that, you could return an OUT_OF_STACK error instead of calling it. Most libraries/functions wouldn’t need this, but there are C libraries which place an extraordinary importance on reliability, and it seems like it would be a useful feature for them.

There might be other reasons why these functions shouldn’t be in the standard (or are impossible on some platforms), but ”the information is worthless” is not one of them. Of course this information can be useful.

The information is indeed worthless unless the standard were to also define such things as the stack layout and a closed set of operations which are allowed to consume more stack, such as defining a VLA, or calling a function.

https://news.ycombinator.com/item?id=28683773 gives a useful way to employ them; Chicken Scheme has to run a minor garbage collection and longjmp to its trampoline before the stack runs out, but because there's no way to find out what the stack size limit is at runtime, you have to configure a stack size limit when you compile it. The CPython interpreter could also use them usefully; in order to ensure that recursive loops in Python programs raise a Python exception instead of segfaulting, it defaults to a limit of only 1000 levels of Python recursion, because some platforms it ran on were segfaulting at 2000. If it could query the stack size limit, it could instead raise an exception when it's getting close to the real limit instead of guessing. They wouldn't be like access().

There are more hacks in Heaven and Earth, Horatio, than are dreamed of in your philosophy.

I believe we were discussing a potential addition to the C standard. It would however be useless unless the standard also defined such things as stack layout and a closed set of operations which may consume more stack space, such as calling a function.

It's true that this potential addition to the C standard would not permit things like CPython or Chicken to depend only on the C standard, it's true, but then every C program already depends on things other than the C standard—such as the example given in TFA, that any C implementation is entitled to abort any C program because it ran out of stack.

Moreover, every nontrivial C program in practice contains UB.

Nevertheless, it does matter what is and isn't standardized; standardizing such functions would greatly improve the situation for programs like those I mention, because they would be able to rely on the C standard to find out when they're about to run out of stack, an event they already have code for handling. It's true that a pathological C library implementation could still totally break their stack-exhaustion-handling code, and in fact that's already true, but fortunately there are lots of C library implementations that behave well enough in practice.

It seems to me that in the case of the x86, the virtual memory system could detect overrunning the end of the stack and announce it to you.

The meta-problem is what to do with the information.

A clean / clear error would already be better than just segfaulting with no indication (that's why e.g. Ruby or Python have explicit stack depth check and will raise an exception hopefully before they run out of C stack).

As mentioned in the OP though, there is zero guarantee about the stack usage by library functions.

No, but that's a pretty weak argument not to have them: they're better than nothing. Not all code uses libraries. And if it was part of the C standard, libraries could use them as well: libraries could fail gracefully instead of blowing the stack. Many libraries already do this when malloc fails, after all.

I have yet to see a library that fails gracefully when malloc fails. Many claim to be able to do so, but usually keel over when actually presented with a failure.

...or much of anything else. I've seen commercial libraries monkey with processor state in some nasty ways.

There is also no guarantee that the stack is contiguous—see the "-fsplit-stack" GCC option, or search for "segmented stacks". Libraries for coroutines and delimited continuations also routinely segment the stack. A simple API based around easy access to "top of stack", "bottom of stack", and "current stack pointer" addresses is thus non-universal. There may not be a meaningful limit to the amount of stack available, aside from available heap memory or address space. And this can change over time in response to actions other than allocating or freeing memory on the stack.

Reply on news.ycombinator.com