[BradSwain]

> On modern "hosted" OSes, there are safeguards about stack overflows, which will quickly kill your process.

There are lots of contexts where a processing being killed is bad.

Sending a deeply nested JSON object as part of a request to some API should not crash the server that handles the request.

In contexts where availability matters, recursing on user supplied input is dangerous.

[kazinator]

You can fairly easily recurse with a context argument in which you maintain a depth count.

  int recursive_fun(rec_context *ctx, ...)
  {
    int res = 0;
    if (++ctx->depth > REC_LIMIT)
       return ERROR_RECURSION_LIMIT;
    ...
       res = recursive_fun(ctx, ...);

    out:
      ctx->depth--;
      return res;
  }

However, a problem with recursion might be something other than the maximum depth reached.

If recursion traverses an exponentially sized abstract space, it can chew up a lot of processing time before going anywhere near the protective limit.

[int_19h]

The other problem, especially for libraries, is that they don't know either the overall stack size nor the size of a single stack frame (the former is specified when linking the executable, the latter is an implementation detail and subject to optimizer's trickery).

Many "fixes" for recursion effectively re-implement it, but do so with their own data structures that are equivalent to the stack (as originally used) but have precise definitions and therefore can be controlled wrt resources used.

[kazinator]

If all the recursive code is under your control (no external libs at the bottom, or, worse, trips through external libs and back into recursion), you can make some generous estimate of the upper bound of a stack frame.

If the OS provides ample stack space, you can inquire about the limit, and subtract a safety margin from that to create your own soft limit that you can test against in the recursion.

Another way is to be absolutely restrictive, rather than track the limit. Create some test cases representing the worst recursive cases you're willing to handle (and document as such). Empirically measure their stack use. Multiply that by 1.5 and use that as the stack check limit.

On startup you can check that this soft limit is not too close to the real one and diagnose the situation.

If your soft limit is many megabytes away from the real one, you're not likely to hit the real one, unless something really stupid happens, like alloca, or a call into some code you don't control that goes rampant.

The submitted article, by the way, could use more nuance like this. Careless recursion in C, without reasoning about the consequences (what happens for certain inputs) is obviously bad, not recursion itself.

[throwaway2037]

    > Careless recursion in C... is obviously bad

Keeping the focus specifically on this bug: Do you think it was "careless recursion" in libexpat? That library was started in 1997, and the recursion bug wasn't found until 2022.

    > Another way is to be absolutely restrictive, rather than track the limit. Create some test cases representing the worst recursive cases you're willing to handle (and document as such). Empirically measure their stack use. Multiply that by 1.5 and use that as the stack check limit.

We look forward to your patches for libexpat to add new unit tests.

[knome]

Which is why it's reasonable to have configurable limits for both processing space and time in anything handling untrusted data.

[kazinator]

Unixes give us that. You have to fork the computation to have it contained in its own process, whose run-time, virtual memory limit, and stack depth you can control.

Doing it all in your VM/runtime, so you can bail the computation with an exception, is more challenging.

[BradSwain]

> Unixes give us that. You have to fork the computation to have it contained in its own process

Is forking a new process on each call to a recursive function practical?

[amiga386]

> Sending a deeply nested JSON object as part of a request to some API should not crash the server that handles the request.

But the API should have limits. For example, respond 413 Payload Too Large if the request is beyond any normal size for that API. Document the limits to API users. You now have an upper bound of how much nesting can be in the user input.

[BradSwain]

I agree. I use the word dangerous to mean there are risks that need to be considered, not that recursion should never be used under any circumstances.

In the general case though, recursion can be tricky to think through, the stack is small, and malicious inputs can be very creative.