Re: bash core dumps doing glob pattern on long string

[Phi Debian]

On Tue, Oct 11, 2022 at 7:23 AM Martin D Kealey <martin@kurahaupo.gen.nz>
wrote:

>
> 4) compile globs into state machines, the same way that regexes get
> compiled, so that they can be matched without needing any recursion.
>
> -Martin
>

Do you mean the NFA colud trade recursion for malloc()'d backtracking point
record? this would trade stacksize vs bss size. Or may be you mean
converting the NFA into DFA, that I could not handle myself :)

That's why at first I thought limiting the input string length was may be
an option, but Chet demonstrated it was not.

Then returning an error instead of core dumps on recursion too deep on the
NFA walk seems to be the thing to do, and then I thought a stack
availabitly check for a given recursive level could be done, this is pretty
easy to do and almost costless regarding perf, specially because bash (and
other shells) have access to alloca(), well we could admit that os/arch
sans alloca() could still core dump.

A stack check with alloca() ressemble something along this lines

int stack_too_small(size_t s)
{ return alloca(s)!=NULL;
}

This non inlinable function do allocate the stack provision, return true if
not possible, false if possible and return the provision to the stack, the
caller is then assured there is enough space in the stack for its recursion
frame.

and the shell code would look like
... recursive_func(...)
{...
  if(stack_too_small(recursion_frame_size)
  { handle nicely; // longjmp, return....
}

What Chet call the right size to define is possibly something like the
recursion frame size, that is the stack needed by the current recursion
level instance (its locals) + all the frame size sub function would need
until the next recurence, i.e if the call path look like

a()-->b()-->c()-->a()...
The recursion frame size  is sum(framesize(a)+framesize(b)+framesize(c))

Some empiric constant can also be used, for instance on linux a max
stacksize of 0x800000 is pretty common deciding we big constant like
32K could be simple and good enough.