new way to control stack overflow, controling only total size of the stack

10 files changed, 100 insertions, 78 deletions

diff --git a/lapi.c b/lapi.c
index 6f33c950..1873bec3 100644
--- a/lapi.c
+++ b/lapi.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lapi.c,v 2.83 2009/06/18 18:59:18 roberto Exp roberto $
+** $Id: lapi.c,v 2.84 2009/06/19 14:21:23 roberto Exp roberto $
 ** Lua API
 ** See Copyright Notice in lua.h
 */
@@ -86,14 +86,15 @@ LUA_API int lua_checkstack (lua_State *L, int size) {
   int res = 1;
   CallInfo *ci = L->ci;
   lua_lock(L);
-  if (size > LUAI_MAXCSTACK ||
-      (L->top - (ci->func + 1) + size) > LUAI_MAXCSTACK)
-    res = 0;  /* stack overflow */
-  else if (size > 0) {
-    luaD_checkstack(L, size);
-    if (ci->top < L->top + size)
-      ci->top = L->top + size;
+  if (L->stack_last - L->top <= size) {  /* need to grow stack? */
+    int inuse = L->top - L->stack + EXTRA_STACK;
+    if (inuse > LUAI_MAXSTACK - size)  /* can grow without overflow? */
+      res = 0;  /* no */
+    else
+      luaD_growstack(L, size);
   }
+  if (res && ci->top < L->top + size)
+    ci->top = L->top + size;  /* adjust frame top */
   lua_unlock(L);
   return res;
 }
diff --git a/lauxlib.c b/lauxlib.c
index f021686a..0ba32e1e 100644
--- a/lauxlib.c
+++ b/lauxlib.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lauxlib.c,v 1.187 2009/06/18 18:59:58 roberto Exp roberto $
+** $Id: lauxlib.c,v 1.188 2009/06/19 14:21:57 roberto Exp roberto $
 ** Auxiliary functions for building Lua libraries
 ** See Copyright Notice in lua.h
 */
@@ -106,9 +106,16 @@ static void pushfuncname (lua_State *L, lua_Debug *ar) {
 
 static int countlevels (lua_State *L) {
   lua_Debug ar;
-  int level = 1;
-  while (lua_getstack(L, level, &ar)) level++;
-  return level;
+  int li = 1, le = 1;
+  /* find an upper bound */
+  while (lua_getstack(L, le, &ar)) { li = le; le *= 2; }
+  /* do a binary search */
+  while (li < le) {
+    int m = (li + le)/2;
+    if (lua_getstack(L, m, &ar)) li = m + 1;
+    else le = m;
+  }
+  return le - 1;
 }
 
 
@@ -263,9 +270,13 @@ LUALIB_API int luaL_checkoption (lua_State *L, int narg, const char *def,
 }
 
 
-LUALIB_API void luaL_checkstack (lua_State *L, int space, const char *mes) {
-  if (!lua_checkstack(L, space))
-    luaL_error(L, "stack overflow (%s)", mes);
+LUALIB_API void luaL_checkstack (lua_State *L, int space, const char *msg) {
+  if (!lua_checkstack(L, space)) {
+    if (msg)
+      luaL_error(L, "stack overflow (%s)", msg);
+    else
+      luaL_error(L, "stack overflow");
+  }
 }
 
 
diff --git a/ldo.c b/ldo.c
index dc9112a1..e93f68e3 100644
--- a/ldo.c
+++ b/ldo.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ldo.c,v 2.64 2009/05/21 20:06:11 roberto Exp roberto $
+** $Id: ldo.c,v 2.65 2009/06/01 19:09:26 roberto Exp roberto $
 ** Stack and Call structure of Lua
 ** See Copyright Notice in lua.h
 */
@@ -70,12 +70,6 @@ void luaD_seterrorobj (lua_State *L, int errcode, StkId oldtop) {
 }
 
 
-static void restore_stack_limit (lua_State *L) {
-  if (L->nci >= LUAI_MAXCALLS)  /* stack overflow? */
-    luaE_freeCI(L);  /* erase all extras CIs */
-}
-
-
 void luaD_throw (lua_State *L, int errcode) {
   if (L->errorJmp) {  /* thread has an error handler? */
     L->errorJmp->status = errcode;  /* set status */
@@ -130,25 +124,63 @@ static void correctstack (lua_State *L, TValue *oldstack) {
 }
 
 
+/* some space for error handling */
+#define ERRORSTACKSIZE  (LUAI_MAXSTACK + 200)
+
+
 void luaD_reallocstack (lua_State *L, int newsize) {
   TValue *oldstack = L->stack;
   int lim = L->stacksize;
-  int realsize = newsize + 1 + EXTRA_STACK;
-  lua_assert(L->stack_last - L->stack == L->stacksize - EXTRA_STACK - 1);
-  luaM_reallocvector(L, L->stack, L->stacksize, realsize, TValue);
-  for (; lim < realsize; lim++)
+  lua_assert(newsize <= LUAI_MAXSTACK || newsize == ERRORSTACKSIZE);
+  lua_assert(L->stack_last - L->stack == L->stacksize - EXTRA_STACK);
+  luaM_reallocvector(L, L->stack, L->stacksize, newsize, TValue);
+  for (; lim < newsize; lim++)
     setnilvalue(L->stack + lim); /* erase new segment */
-  L->stacksize = realsize;
-  L->stack_last = L->stack+newsize;
+  L->stacksize = newsize;
+  L->stack_last = L->stack + newsize - EXTRA_STACK;
   correctstack(L, oldstack);
 }
 
 
 void luaD_growstack (lua_State *L, int n) {
-  if (n <= L->stacksize)  /* double size is enough? */
-    luaD_reallocstack(L, 2*L->stacksize);
+  int size = L->stacksize;
+  if (size > LUAI_MAXSTACK)  /* error after extra size? */
+    luaD_throw(L, LUA_ERRERR);
+  else {
+    int needed = L->top - L->stack + n + EXTRA_STACK;
+    int newsize = 2 * size;
+    if (newsize > LUAI_MAXSTACK) newsize = LUAI_MAXSTACK;
+    if (newsize < needed) newsize = needed;
+    if (newsize > LUAI_MAXSTACK) {  /* stack overflow? */
+      luaD_reallocstack(L, ERRORSTACKSIZE);
+      luaG_runerror(L, "stack overflow");
+    }
+    else
+      luaD_reallocstack(L, newsize);
+  }
+}
+
+
+static int stackinuse (lua_State *L) {
+  CallInfo *ci;
+  StkId lim = L->top;
+  for (ci = L->ci; ci != NULL; ci = ci->previous) {
+    lua_assert(ci->top <= L->stack_last);
+    if (lim < ci->top) lim = ci->top;
+  }
+  return cast_int(lim - L->stack) + 1;  /* part of stack in use */
+}
+
+
+void luaD_shrinkstack (lua_State *L) {
+  int inuse = stackinuse(L);
+  int goodsize = inuse + (inuse / 8) + 2*EXTRA_STACK;
+  if (goodsize > LUAI_MAXSTACK) goodsize = LUAI_MAXSTACK;
+  if (inuse > LUAI_MAXSTACK ||  /* handling stack overflow? */
+      goodsize >= L->stacksize)  /* would grow instead of shrink? */
+    condmovestack(L);  /* don't change stack (change only for debugging) */
   else
-    luaD_reallocstack(L, L->stacksize + n);
+    luaD_reallocstack(L, goodsize);  /* shrink it */
 }
 
 
@@ -427,7 +459,7 @@ static int recover (lua_State *L, int status) {
   L->ci = ci;
   L->allowhook = ci->u.c.old_allowhook;
   L->nny = 0;  /* should be zero to be yieldable */
-  restore_stack_limit(L);
+  luaD_shrinkstack(L);
   L->errfunc = ci->u.c.old_errfunc;
   ci->callstatus |= CIST_STAT;  /* call has error status */
   ci->u.c.status = status;  /* (here it is) */
@@ -499,7 +531,7 @@ int luaD_pcall (lua_State *L, Pfunc func, void *u,
     L->ci = old_ci;
     L->allowhook = old_allowhooks;
     L->nny = old_nny;
-    restore_stack_limit(L);
+    luaD_shrinkstack(L);
   }
   L->errfunc = old_errfunc;
   return status;
diff --git a/ldo.h b/ldo.h
index 6cd9fdca..7f12ff85 100644
--- a/ldo.h
+++ b/ldo.h
@@ -1,5 +1,5 @@
 /*
-** $Id: ldo.h,v 2.13 2009/06/08 19:35:59 roberto Exp roberto $
+** $Id: ldo.h,v 2.14 2009/07/08 16:06:51 roberto Exp roberto $
 ** Stack and Call structure of Lua
 ** See Copyright Notice in lua.h
 */
@@ -37,6 +37,7 @@ LUAI_FUNC int luaD_poscall (lua_State *L, StkId firstResult);
 LUAI_FUNC void luaD_reallocCI (lua_State *L, int newsize);
 LUAI_FUNC void luaD_reallocstack (lua_State *L, int newsize);
 LUAI_FUNC void luaD_growstack (lua_State *L, int n);
+LUAI_FUNC void luaD_shrinkstack (lua_State *L);
 
 LUAI_FUNC void luaD_throw (lua_State *L, int errcode);
 LUAI_FUNC int luaD_rawrunprotected (lua_State *L, Pfunc f, void *ud);
diff --git a/llimits.h b/llimits.h
index 5f254f72..c4220d67 100644
--- a/llimits.h
+++ b/llimits.h
@@ -1,5 +1,5 @@
 /*
-** $Id: llimits.h,v 1.71 2009/06/08 19:35:59 roberto Exp roberto $
+** $Id: llimits.h,v 1.72 2009/07/01 16:14:15 roberto Exp roberto $
 ** Limits, basic types, and some other `installation-dependent' definitions
 ** See Copyright Notice in lua.h
 */
@@ -122,8 +122,8 @@ typedef lu_int32 Instruction;
 #ifndef HARDSTACKTESTS
 #define condmovestack(L)        ((void)0)
 #else
-#define condmovestack(L) /* realloc stack keeping its size */ \
-        luaD_reallocstack((L), (L)->stacksize - EXTRA_STACK - 1)
+/* realloc stack keeping its size */
+#define condmovestack(L)        luaD_reallocstack((L), (L)->stacksize)
 #endif
 
 #endif
diff --git a/lstate.c b/lstate.c
index 3268209e..0b9bb671 100644
--- a/lstate.c
+++ b/lstate.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.c,v 2.55 2009/06/01 19:09:26 roberto Exp roberto $
+** $Id: lstate.c,v 2.56 2009/06/18 18:59:18 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -52,12 +52,6 @@ CallInfo *luaE_extendCI (lua_State *L) {
   L->ci->next = ci;
   ci->previous = L->ci;
   ci->next = NULL;
-  if (++L->nci >= LUAI_MAXCALLS) {
-    if (L->nci == LUAI_MAXCALLS)  /* overflow? */
-      luaG_runerror(L, "stack overflow");
-    if (L->nci >= LUAI_MAXCALLS + LUAI_EXTRACALLS)  /* again? */
-      luaD_throw(L, LUA_ERRERR);  /* error while handling overflow */
-  }
   return ci;
 }
 
@@ -69,7 +63,6 @@ void luaE_freeCI (lua_State *L) {
   while ((ci = next) != NULL) {
     next = ci->next;
     luaM_free(L, ci);
-    L->nci--;
   }
 }
 
@@ -77,12 +70,12 @@ void luaE_freeCI (lua_State *L) {
 static void stack_init (lua_State *L1, lua_State *L) {
   int i;
   /* initialize stack array */
-  L1->stack = luaM_newvector(L, BASIC_STACK_SIZE + EXTRA_STACK, TValue);
-  L1->stacksize = BASIC_STACK_SIZE + EXTRA_STACK;
-  for (i = 0; i < BASIC_STACK_SIZE + EXTRA_STACK; i++)
+  L1->stack = luaM_newvector(L, BASIC_STACK_SIZE, TValue);
+  L1->stacksize = BASIC_STACK_SIZE;
+  for (i = 0; i < BASIC_STACK_SIZE; i++)
     setnilvalue(L1->stack + i);  /* erase new stack */
   L1->top = L1->stack;
-  L1->stack_last = L1->stack+(L1->stacksize - EXTRA_STACK)-1;
+  L1->stack_last = L1->stack + L1->stacksize - EXTRA_STACK;
   /* initialize first ci */
   L1->ci->func = L1->top;
   setnilvalue(L1->top++);  /* 'function' entry for this 'ci' */
@@ -94,7 +87,6 @@ static void stack_init (lua_State *L1, lua_State *L) {
 static void freestack (lua_State *L) {
   L->ci = &L->base_ci;  /* reset 'ci' list */
   luaE_freeCI(L);
-  lua_assert(L->nci == 0);
   luaM_freearray(L, L->stack, L->stacksize);
 }
 
@@ -131,7 +123,6 @@ static void preinit_state (lua_State *L, global_State *g) {
   L->status = LUA_OK;
   L->base_ci.next = L->base_ci.previous = NULL;
   L->ci = &L->base_ci;
-  L->nci = 0;
   L->errfunc = 0;
   setnilvalue(gt(L));
 }
diff --git a/lstate.h b/lstate.h
index 783e51cf..2ddffaf1 100644
--- a/lstate.h
+++ b/lstate.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.h,v 2.44 2009/06/01 19:09:26 roberto Exp roberto $
+** $Id: lstate.h,v 2.45 2009/06/18 18:59:18 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -163,7 +163,6 @@ struct lua_State {
   StkId top;  /* first free slot in the stack */
   global_State *l_G;
   CallInfo *ci;  /* call info for current function */
-  int nci;  /* number of total CallInfo structures linked */
   const Instruction *oldpc;  /* last pc traced */
   StkId stack_last;  /* last free slot in the stack */
   StkId stack;  /* stack base */
diff --git a/ltests.c b/ltests.c
index bc5a21e0..cfa14c21 100644
--- a/ltests.c
+++ b/ltests.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltests.c,v 2.65 2009/06/15 19:51:31 roberto Exp roberto $
+** $Id: ltests.c,v 2.66 2009/06/17 17:53:14 roberto Exp roberto $
 ** Internal Module for Debugging of the Lua Implementation
 ** See Copyright Notice in lua.h
 */
@@ -570,7 +570,6 @@ static int stacklevel (lua_State *L) {
   unsigned long a = 0;
   lua_pushinteger(L, (L->top - L->stack));
   lua_pushinteger(L, (L->stack_last - L->stack));
-  lua_pushinteger(L, L->nci);
   lua_pushinteger(L, (unsigned long)&a);
   return 5;
 }
diff --git a/lua.h b/lua.h
index edeafe7a..5887d16c 100644
--- a/lua.h
+++ b/lua.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lua.h,v 1.239 2009/06/17 17:49:44 roberto Exp roberto $
+** $Id: lua.h,v 1.240 2009/06/18 18:59:18 roberto Exp roberto $
 ** Lua - An Extensible Extension Language
 ** Lua.org, PUC-Rio, Brazil (http://www.lua.org)
 ** See Copyright Notice at the end of this file
@@ -33,7 +33,7 @@
 /*
 ** pseudo-indices
 */
-#define LUA_REGISTRYINDEX       (-(LUAI_MCS_AUX) - 1)
+#define LUA_REGISTRYINDEX       LUAI_FIRSTPSEUDOIDX
 #define LUA_ENVIRONINDEX        (LUA_REGISTRYINDEX - 1)
 #define LUA_GLOBALSINDEX        (LUA_ENVIRONINDEX - 1)
 #define lua_upvalueindex(i)     (LUA_GLOBALSINDEX-(i))
diff --git a/luaconf.h b/luaconf.h
index 96dacdda..d8bcc2ba 100644
--- a/luaconf.h
+++ b/luaconf.h
@@ -1,5 +1,5 @@
 /*
-** $Id: luaconf.h,v 1.105 2009/06/18 18:19:36 roberto Exp roberto $
+** $Id: luaconf.h,v 1.106 2009/07/01 16:16:40 roberto Exp roberto $
 ** Configuration file for Lua
 ** See Copyright Notice in lua.h
 */
@@ -417,31 +417,19 @@
 
 
 /*
-@@ LUAI_MAXCALLS limits the number of nested calls.
-** CHANGE it if you need really deep recursive calls. This limit is
-** arbitrary; its only purpose is to stop infinite recursion before
-** exhausting memory.
-*/
-#define LUAI_MAXCALLS   20000
-
-
-/*
-@@ LUAI_MAXCSTACK limits the number of Lua stack slots that a C function
-@* can use.
+@@ LUAI_MAXSTACK limits the size of the Lua stack.
 ** CHANGE it if you need a different limit. This limit is arbitrary;
-** its only purpose is to stop C functions to consume unlimited stack
-** space.
+** its only purpose is to stop Lua to consume unlimited stack
+** space (and to reserve some numbers for pseudo-indices).
 */
-/* life is simpler if stack size fits in an int (16 is an estimate
-   for the size of a Lua value) */
-#if SHRT_MAX < (INT_MAX / 16)
-#define LUAI_MCS_AUX    SHRT_MAX
+#if LUAI_BITSINT >= 32
+#define LUAI_MAXSTACK           1000000
 #else
-#define LUAI_MCS_AUX    (INT_MAX / 16)
+#define LUAI_MAXSTACK           15000
 #endif
 
-/* reserve some space for pseudo-indices */
-#define LUAI_MAXCSTACK  (LUAI_MCS_AUX - 1000)
+/* reserve some space for error handling */
+#define LUAI_FIRSTPSEUDOIDX  (-LUAI_MAXSTACK - 1000)