Karim BELABAS on Thu, 21 Oct 1999 15:11:05 +0200 (MET DST)


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: infinite recursion?


> [Karim:]
> > GP signal handler gets called at this point, but it also needs a stack
> > frame and there's no room for that. Hence a SEGV is .... Boom.
> > 
> > I see no nice portable way out of this (there's sigaltstack on Solaris as
> > Igor pointed), except by having a new default "recurdepth" that would
> > specify a maximal recursion depth for GP functions (as in Maple, except its
> > value seems to be hardcoded and not user-modifiable).
[Ilya:]
> Perl's Regular Expression engine has/had the same problem.  A month
> (or two?) ago somebody send a patch with a portable workaround: get
> the stack boundary from OS (it has Configure patches too ;-), and
> complain if we are close to the bottom of the pit.  Look on
> 
> http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/

I like the idea (it's a hack, but a nice one).

The following patch checks if [gs]etrlimit exists on the system [ it should
also check that the stack grows downward, but currently doesn't ]. And if
so defines STACK_CHECK in paricfg.h. Consequently, GP checks if we're not
running of (system's not PARI's) stack space everytime a routine is called
(in src/language/anal.c:identifier()).

(14:46) gp > g()=g()
(14:46) gp > g
  ***   deep recursion: g()
                        ^---
It doesn't affect library mode program, although this can easily be done by
the programmer.

Apparently, on SunOS 5.5.1 (SUNW, Ultra-1), setrlimit(RLIMIT_STACK, ...)
doesn't work: it reports success, subsequent getrlimit report the intended
new value, but the process receives a SEGV nevertheless when it reaches the
_original_ limit (around 8.4MB on my machine), not the new one. So I had to
disable the routine src/language/init.c:pari_stackgrow() which tried to
increase stack space if possible. Can somebody 

1) either point out an obvious mistake on my part in this routine

2) or test it on other systems than mine by removing the #ifdef'ed out part
in pari_stackgrow, to see whether it's only a Solaris bug

Right now (i.e with stack growing disabled), recursion depth is now limited
by about 4000 on my machine. [ but it dumped core before, so... ]

Since the patch looks at worst harmless, I committed it to the archive.

  Karim.

Index: Configure
===================================================================
RCS file: /home/megrez/cvsroot/pari/Configure,v
retrieving revision 1.6
diff -c -r1.6 Configure
*** Configure	1999/10/18 16:11:58	1.6
--- Configure	1999/10/21 13:07:40
***************
*** 1050,1055 ****
--- 1050,1056 ----
  list='getrusage times ftime'; . ./look
  list='sigrelse sigsetmask'; . ./look
  list=TIOCGWINSZ; . ./look
+ list=getrlimit; . ./look
  
  # For install(). Do we need libdl.so?
  # on irix and osf1 -ldl not needed
Index: config/paricfg.h.SH
===================================================================
RCS file: /home/megrez/cvsroot/pari/config/paricfg.h.SH,v
retrieving revision 1.2
diff -c -r1.2 paricfg.h.SH
*** config/paricfg.h.SH	1999/09/20 16:39:33	1.2
--- config/paricfg.h.SH	1999/10/21 13:07:40
***************
*** 134,139 ****
--- 134,143 ----
  ;;
  esac
  
+ case $has_getrlimit in
+ yes) echo '#define STACK_CHECK' >> $file;;
+ esac
+ 
  case $has_TIOCGWINSZ in
  yes) echo '#define HAS_TIOCGWINSZ' >> $file;;
  esac
Index: src/language/anal.c
===================================================================
RCS file: /home/megrez/cvsroot/pari/src/language/anal.c,v
retrieving revision 1.4
diff -c -r1.4 anal.c
*** src/language/anal.c	1999/10/19 17:30:13	1.4
--- src/language/anal.c	1999/10/21 13:07:40
***************
*** 45,50 ****
--- 45,51 ----
  static entree *skipentry(void);
  
  void killbloc0(GEN x, int inspect);
+ int pari_stackgrow(void);
  
  /* last time we began parsing an object of specified type */
  static struct
***************
*** 1255,1260 ****
--- 1256,1267 ----
      return matrix_block((GEN) ep->value,ep);
    }
    ep = do_alias(ep); matchcomma = 0;
+ #ifdef STACK_CHECK
+   if (PARI_stack_limit
+     && (void*) &ptr <= PARI_stack_limit
+     && !pari_stackgrow())
+       err(talker2, "deep recursion", mark.identifier, mark.start);
+ #endif
    if (ep->code)
    {
      char *s = ep->code, *oldanalyseur = NULL, *buf, *limit, *bp;
Index: src/language/anal.h
===================================================================
RCS file: /home/megrez/cvsroot/pari/src/language/anal.h,v
retrieving revision 1.1.1.1
diff -c -r1.1.1.1 anal.h
*** src/language/anal.h	1999/09/16 13:48:02	1.1.1.1
--- src/language/anal.h	1999/10/21 13:07:40
***************
*** 81,86 ****
--- 81,90 ----
  /* are we under emacs ? (might change output) */
  extern int under_emacs;
  
+ #ifdef STACK_CHECK
+ extern void *PARI_stack_limit;
+ #endif
+ 
  /* entrees */
  #define Epstatic 0x100
  #define EpVALENCE(ep) ((ep)->valence & 0xFF)
Index: src/language/init.c
===================================================================
RCS file: /home/megrez/cvsroot/pari/src/language/init.c,v
retrieving revision 1.6
diff -c -r1.6 init.c
*** src/language/init.c	1999/10/18 12:05:03	1.6
--- src/language/init.c	1999/10/21 13:07:40
***************
*** 46,56 ****
  void  initout(void);
  int   term_width(void);
  
  /*********************************************************************/
  /*                                                                   */
! /*                     INITIALISATION DU SYSTEME                     */
  /*                                                                   */
  /*********************************************************************/
  static int var_not_changed; /* altered in reorder() */
  static int try_to_recover = 0;
  static long next_bloc;
--- 46,112 ----
  void  initout(void);
  int   term_width(void);
  
+ #ifdef STACK_CHECK
  /*********************************************************************/
  /*                                                                   */
! /*                       C STACK SIZE CONTROL                        */
! /*             (to avoid core dump on deep recursion)                */
  /*                                                                   */
  /*********************************************************************/
+ 
+ /* adapted from Perl code written by Dominic Dunlop */
+ #include <sys/resource.h>
+ void *PARI_stack_limit = NULL;
+ 
+ /* Set PARI_stack_limit to (a little above) the lowest safe address that can
+  * be used on the stack. Leave PARI_stack_limit at its initial value (NULL)
+  * to show no check should be made [pari_init_stackcheck failed].
+  */
+ static void
+ pari_init_stackcheck(void *stack_base)
+ {
+   struct rlimit rip;
+ 
+   if (getrlimit(RLIMIT_STACK, &rip))
+      return;
+ 
+   PARI_stack_limit = stack_base - (rip.rlim_cur/16)*15;
+   return;
+ }
+ 
+ /* Attempt to grow the main (or only) stack allocation to 3/2 times its
+  * present size, adjusting PARI_stack_limit accordingly.
+  */
+ int
+ pari_stackgrow(void)
+ {
+ #if 0
+   struct rlimit rip1, rip2;  /* Two copies, so we don't have to */
+                              /* care about member size. */
+   if (getrlimit(RLIMIT_STACK, &rip1) ||
+      (rip1.rlim_max != RLIM_INFINITY && rip1.rlim_cur >= rip1.rlim_max))
+     return 0;
+ 
+   rip2.rlim_cur = (rip1.rlim_cur/2)*3;
+   rip2.rlim_max = rip1.rlim_max;
+   if (rip2.rlim_max != RLIM_INFINITY && rip2.rlim_cur > rip2.rlim_max)
+     rip2.rlim_cur = rip2.rlim_max;
+   if (setrlimit(RLIMIT_STACK, &rip2)) return 0;
+ 
+   PARI_stack_limit -= rip2.rlim_cur - rip1.rlim_cur;
+   return 1;
+ #else
+   return 0;
+ #endif
+ }
+ 
+ #endif /* STACK_CHECK */
+ 
+ /*********************************************************************/
+ /*                                                                   */
+ /*                       SYSTEM INITIALIZATION                       */
+ /*                                                                   */
+ /*********************************************************************/
  static int var_not_changed; /* altered in reorder() */
  static int try_to_recover = 0;
  static long next_bloc;
***************
*** 296,301 ****
--- 352,360 ----
    long n;
    GEN p;
  
+ #ifdef STACK_CHECK
+   pari_init_stackcheck(&n);
+ #endif
    init_defaults(0);
    if (INIT_JMP && setjmp(environnement))
    {
__
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://hasse.mathematik.tu-muenchen.de/ntsw/pari/