[hughw]

Please leave recursion to math and keep it out of (in particular C) software: it kills and will kill again.

Is the whole (tail-recursion optimized) Lisp language family subject to DOS? Just check that you terminate at some point, right? "Recursion kills" is just too broad and not helpful.

[Etheryte]

The whole point of this CVE is what do you do when the input you're parsing is so large that you run out of space before you can terminate. Tail recursion helps in the sense that the issue will happen later, but it isn't a fix when we're talking about arbitrary data like an XML parser.

[MattPalmer1086]

No, this CVE is explicitly about recursive calls overflowing the stack, not running out of memory on large inputs.

The point of tail recursion is that it can be converted into a loop instead of actually recursing.

[pajko]

Exactly. A stack overflow caused by recursion more likely converts to an endless loop. Nothing saves a bad code design.

[Etheryte]

I did not mention memory once anywhere in my comment?

[MattPalmer1086]

My apologies, I interpreted "running out of space" as meaning running out of memory, rather than meaning overflowing the stack.

The tail recursion part isn't right though. If it isn't optimised into a loop, then tail recursion makes no difference at all, you will overflow the stack just as rapidly, not later. If it is optimised into a loop, then you will not overflow the stack at all.

[kazinator]

Someone who doesn't believe that stack is "space" will not believe that it's "memory" either. :)

[hughw]

Tail call optimization uses no stack at all

[kazinator]

Therefore it would not be said to use space in proportion to the number of calls that have not returned.

[BalinKing]

I think "space" (i.e. in "run out of space before you can terminate") is most naturally interpreted as referring to memory.

[kazinator]

Stack is memory!

An algorithm that uses an amount of stack proportional to the input N is said to require O(N) space. If it is rewritten to explicitly allocate the storage instead of using stack, it still uses O(N) space.

[jraph]

Not necessarily. If you are computing an aggregation for instance, if your computation is recursive and not tail call optimized, it may overflow the stack but the fixed version will not use additional memory for each iteration.

Otherwise, indeed stack is memory, but the memory in general is usually way less limited than the stack and also running out of memory doesn't have the same security implications as overflowing an unprotected stack.

And, unless you manage to encode everything in the stack, your iterative version will probably take the same amount of memory as your non-optimized recursive version, minus the space used for the stack.

[MattPalmer1086]

True, I'd just tend to call exceeding the stack limit a stack overflow, rather than the more generic running out of space.

[spyc]

Correct.

[ndriscoll]

Reasonable compilers translate tail-recursive functions into loops/jumps, so the stack does not grow. Tail recursion is easier to do in a garbage collected functional language though (e.g. if you need to use continuation passing).

Even in C, the recursive solution is usually simpler, so it makes sense to use it for unit tests to validate the more manual solution.

[spyc]

The point of termination is beyond stack overflow here, that's the problem. And unlike heap, stack does not tell you gently that it's running out.

[fc417fc802]

That really depends. Segmented stack makes it equivalent to heap. Heap might or might not fail gracefully. If the OS permits overcommit and you've mapped a large region, then an arbitrary process on the machine could trigger the OOM when writing to a supposedly allocated (but not previously written) piece of memory.

Presumably you configure resource limits in production but that just means the "correct" process gets unexpectedly killed instead of an arbitrary one.

Code handling arbitrary input needs to carefully limit resource usage. There's no avoiding it.