Avoid C stack overflow

Avoid C stack overflow

[Dmitry Antipov]

[-- Attachment #1: Type: text/plain, Size: 527 bytes --]

In http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16999 the user, guided by interactive
help and documentation, got a crash caused by C stack overflow. What about an attempt
to avoid such a mess by examining current C stack depth and check it against system
limits, like suggested in the patch below?

For those who cares about MS-Windows, this looks like a rough equivalent to
getrlimit (RLIMIT_STACK,...):

http://stackoverflow.com/questions/21754928/how-to-get-stack-size-and-stack-limit-of-any-thread-using-win32-api

Dmitry

[-- Attachment #2: error_if_c_stack_overflow.patch --]
[-- Type: text/x-patch, Size: 1868 bytes --]

=== modified file 'src/eval.c'
--- src/eval.c	2014-02-10 09:48:17 +0000
+++ src/eval.c	2014-03-13 15:02:10 +0000
@@ -33,6 +33,10 @@
 #include "xterm.h"
 #endif
 
+#ifdef HAVE_SYS_RESOURCE_H
+#include <sys/resource.h>
+#endif
+
 /* Chain of condition and catch handlers currently in effect.  */
 
 struct handler *handlerlist;
@@ -240,6 +244,32 @@
 
 static struct handler handlerlist_sentinel;
 
+/* C stack overflow protection.  */
+
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+
+/* Extra stack space to reserve.  */
+#define STACK_EXTRA (128 * 1024)
+
+/* Current C stack slimit.  */
+static struct rlimit stack_limit;
+
+#define STACK_GUARD do {				\
+  ptrdiff_t stack_size;				\
+  if ((char *) &stack_size < stack_bottom)		\
+    stack_size = stack_bottom - (char *) &stack_size;	\
+  else							\
+    stack_size = (char *) &stack_size - stack_bottom;	\
+  if (stack_size + STACK_EXTRA > stack_limit.rlim_cur)	\
+    error ("Attempt to overflow C stack");		\
+  } while (0)
+
+#else /* !HAVE_GETRLIMIT || !RLIMIT_STACK */
+
+#define STACK_GUARD ((void) 0)
+
+#endif /* HAVE_GETRLIMIT && RLIMIT_STACK */
+
 void
 init_eval (void)
 {
@@ -262,6 +292,10 @@
 #endif
   /* This is less than the initial value of num_nonmacro_input_events.  */
   when_entered_debugger = -1;
+#if defined (HAVE_GETRLIMIT) && defined (RLIMIT_STACK)
+  if (getrlimit (RLIMIT_STACK, &stack_limit))
+    emacs_abort ();
+#endif /* HAVE_GETRLIMIT && RLIMIT_STACK */
 }
 
 /* Unwind-protect function used by call_debugger.  */
@@ -2060,6 +2094,8 @@
   Lisp_Object funcar;
   struct gcpro gcpro1, gcpro2, gcpro3;
 
+  STACK_GUARD;
+
   if (SYMBOLP (form))
     {
       /* Look up its binding in the lexical environment.
@@ -2749,6 +2785,8 @@
   register Lisp_Object *internal_args;
   ptrdiff_t i;
 
+  STACK_GUARD;
+
   QUIT;
 
   if (++lisp_eval_depth > max_lisp_eval_depth)

Re: Avoid C stack overflow

[Eli Zaretskii]

> Date: Thu, 13 Mar 2014 20:42:52 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> 
> For those who cares about MS-Windows, this looks like a rough equivalent to
> getrlimit (RLIMIT_STACK,...):
> 
> http://stackoverflow.com/questions/21754928/how-to-get-stack-size-and-stack-limit-of-any-thread-using-win32-api

No, the API used there is only available since Windows 7.

There's a much easier method, which works on all supported versions of
Windows.  So don't worry about this aspect.

Re: Avoid C stack overflow

[Paul Eggert]

On 03/13/2014 09:42 AM, Dmitry Antipov wrote:
> What about an attempt to avoid such a mess by examining current C 
> stack depth and check it against system limits, like suggested in the 
> patch below?

Don't most systems solve the problem with guard pages these days? If so, 
Emacs should just rely on these pages, as that shouldn't require slowing 
down Ffuncall etc. And if not, if memory management is available Emacs 
could install a guard page of its own, again without slowing down the 
main interpreter loop.

Also, the code as given won't work on systems that have split stacks 
(e.g., gcc -fsplit-stack), and would need to be ported to them.

How about the following idea instead?  Assume that there are guard 
pages, and have Emacs trap the resulting signal and do the right thing.

Re: Avoid C stack overflow

[Eli Zaretskii]

> Date: Thu, 13 Mar 2014 10:57:33 -0700
> From: Paul Eggert <eggert@cs.ucla.edu>
> 
> How about the following idea instead?  Assume that there are guard 
> pages, and have Emacs trap the resulting signal and do the right thing.

But "the right thing" is to signal an error and throw to top level,
isn't it?  If so, is it safe to do that from a signal handler?

Re: Avoid C stack overflow

[Paul Eggert]

Eli Zaretskii wrote:
> "the right thing" is to signal an error and throw to top level,
> isn't it?  If so, is it safe to do that from a signal handler?

Probably not.  Perhaps we could engineer our way around that issue, but 
it sounds like it'd be more trouble than it's worth.  (A problem I fear 
that's shared by the other proposals in this thread....)

Re: Avoid C stack overflow

[Dmitry Antipov]

On 03/13/2014 09:57 PM, Paul Eggert wrote:

> Don't most systems solve the problem with guard pages these days? If so, Emacs should just rely on these pages,
> as that shouldn't require slowing down Ffuncall etc. And if not, if memory management is
> available Emacs could install a guard page of its own, again without slowing down the main interpreter loop.

 From GCC manual:

"For most operating systems, gcc does not perform stack overflow checking by default. This means that if the main
environment task or some other task exceeds the available stack space, then unpredictable behavior will occur. Most
native systems offer some level of protection by adding a guard page at the end of each task stack. This mechanism
is usually not enough for dealing properly with stack overflow situations because a large local variable could “jump”
above the guard page. Furthermore, when the guard page is hit, there may not be any space left on the stack for
executing the exception propagation code. Enabling stack checking avoids such situations."

I.e. GCC developers suggests do not rely on guard pages and use -fstack-check.

> Also, the code as given won't work on systems that have split stacks (e.g., gcc -fsplit-stack), and would need
> to be ported to them.

 From alloc.c:

   /* This assumes that the stack is a contiguous region in memory.  If
      that's not the case, something has to be done here to iterate
      over the stack segments.  */
   mark_memory (stack_base, end);

I.e. -fsplit-stack is incompatible with our current GC (if GC_MARK_STACK, which is the default
for most (all?) supported configurations).

Dmitry

Re: Avoid C stack overflow

[Paul Eggert]

Dmitry Antipov wrote:
> GCC developers suggests do not rely on guard pages

The problems they note with guard pages shouldn't apply to Emacs.  Emacs 
isn't supposed to have huge locals that can jump the guard page.  And 
Emacs could handle the signal on a secondary stack by means of 
sigaltstack; this is fairly common practice.

> -fsplit-stack is incompatible with our current GC

Good point, I forgot about the stack-scanning problem.

Re: Avoid C stack overflow

[Dmitry Antipov]

On 03/14/2014 10:59 AM, Paul Eggert wrote:

> Good point, I forgot about the stack-scanning problem.

After reading http://gcc.gnu.org/wiki/SplitStacks and
looking into libgcc sources, this looks reasonably simple:

=== modified file 'src/alloc.c'
--- src/alloc.c 2014-02-28 21:45:34 +0000
+++ src/alloc.c 2014-03-14 11:17:42 +0000
@@ -4866,11 +4866,30 @@
  #endif /* not GC_SAVE_REGISTERS_ON_STACK */
  #endif /* not HAVE___BUILTIN_UNWIND_INIT */

+#ifdef SPLIT_STACK
+
+  /* This assumes gcc >= 4.6.0 with -fsplit-stack
+     and corresponding support in libgcc.  */
+  {
+    size_t stack_size;
+    extern void * __splitstack_find (void *, void *, size_t *,
+                                    void **, void **, void **);
+    void *next_segment = NULL, *next_sp = NULL, *initial_sp = NULL, *stack;
+
+    while ((stack = __splitstack_find (next_segment, next_sp, &stack_size,
+                                      &next_segment, &next_sp, &initial_sp)))
+      mark_memory (stack, (char *) stack + stack_size);
+  }
+
+#else /* not SPLIT_STACK */
+
    /* This assumes that the stack is a contiguous region in memory.  If
       that's not the case, something has to be done here to iterate
       over the stack segments.  */
    mark_memory (stack_base, end);

+#endif /* SPLIT_STACK */
+
    /* Allow for marking a secondary stack, like the register stack on the
       ia64.  */
  #ifdef GC_MARK_SECONDARY_STACK

After compiling with CPPFLAGS='-DSPLIT_STACK' and CFLAGS='-O0 -fsplit-stack -g3',
I even got the binary which doesn't crash immediately (but do it somewhat
later, after a long byte-compile run :-().

Dmitry

Re: Avoid C stack overflow

[Stefan Monnier]

>> GCC developers suggests do not rely on guard pages
> The problems they note with guard pages shouldn't apply to Emacs.
> Emacs isn't supposed to have huge locals that can jump the guard page.

Currently, "MAX_ALLOCA = 16 * 1024", so yes, Emacs is expected to
occasionally allocate objects larger than your typical 4KB or 8KB
guard page.


        Stefan

Re: Avoid C stack overflow

[Paul Eggert]

Stefan Monnier wrote:
> Currently, "MAX_ALLOCA = 16 * 1024", so yes, Emacs is expected to
> occasionally allocate objects larger than your typical 4KB or 8KB
> guard page.

That's easily fixable by adjusting MAX_ALLOCA down to a bit less than 4 
KiB (which is what Gnulib code does) or by arranging for more guard 
pages than usual (more hassle, but eminently doable on most platforms).

Emacs already has a stack-overflow prevention mechanism, right?  And 
we're talking about what to do when the user deliberately disables it? 
So the simplest answer is "don't do that".

Re: Avoid C stack overflow

[Stefan]

> Emacs already has a stack-overflow prevention mechanism, right?

Yes.

> And we're talking about what to do when the user deliberately disables
> it? So the simplest answer is "don't do that".

Actually, when we bump into something like max-lisp-eval-depth, we
could look at the actual C stack size to compute the average "C stack
usage per Lisp eval depth" and from that compute a approximate upper
bound on the maximum safe value of max-lisp-eval-depth.


        Stefan

Re: Avoid C stack overflow

[Stephen J. Turnbull]

Stefan writes:

 > > Emacs already has a stack-overflow prevention mechanism, right?
 > 
 > Yes.
 > 
 > > And we're talking about what to do when the user deliberately disables
 > > it? So the simplest answer is "don't do that".
 > 
 > Actually, when we bump into something like max-lisp-eval-depth, we
 > could look at the actual C stack size to compute the average "C stack

Surely you want a worst-case-experienced-in-practice estimate here.
So you should collect data on *variation* of the ratio of C stack size
to max-lisp-eval-depth as well.

N.B. Unless the stack is extremely well-behaved across Lisp programs,
you're computing max-lisp-eval-depth to stack size for the case where
you hit max-lisp-eval-depth.  It might very well be that this is quite
different from cases where you don't.  I don't know if this *matters*
in any practical application to Emacs development, probably not.  But
I don't know what other uses people might find for this statistic.

 > usage per Lisp eval depth" and from that compute a approximate upper
 > bound on the maximum safe value of max-lisp-eval-depth.