summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2016-04-19 09:34:08 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2016-04-19 09:34:08 -0300
commit89c09c8e400806a2059fe8460c7c9db517d16ed7 (patch)
tree78abde0f26d7c9a4d1bd9dce15bb51ea768cd7fc
parent48baa5e89cfd7e7fbfe03966b50bfcf4f57cc6cd (diff)
downloadlua-89c09c8e400806a2059fe8460c7c9db517d16ed7.tar.gz
lua-89c09c8e400806a2059fe8460c7c9db517d16ed7.tar.bz2
lua-89c09c8e400806a2059fe8460c7c9db517d16ed7.zip
match time limit defined by variable 'string.pattlimit'
-rw-r--r--lstrlib.c52
1 files changed, 36 insertions, 16 deletions
diff --git a/lstrlib.c b/lstrlib.c
index 29e6a250..a26455d5 100644
--- a/lstrlib.c
+++ b/lstrlib.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: lstrlib.c,v 1.244 2016/04/07 15:40:07 roberto Exp roberto $ 2** $Id: lstrlib.c,v 1.245 2016/04/08 21:15:02 roberto Exp roberto $
3** Standard library for string operations and pattern-matching 3** Standard library for string operations and pattern-matching
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -26,7 +26,8 @@
26 26
27/* 27/*
28** maximum number of captures that a pattern can do during 28** maximum number of captures that a pattern can do during
29** pattern-matching. This limit is arbitrary. 29** pattern-matching. This limit is arbitrary, but must fit in
30** an unsigned char.
30*/ 31*/
31#if !defined(LUA_MAXCAPTURES) 32#if !defined(LUA_MAXCAPTURES)
32#define LUA_MAXCAPTURES 32 33#define LUA_MAXCAPTURES 32
@@ -214,9 +215,10 @@ typedef struct MatchState {
214 const char *src_end; /* end ('\0') of source string */ 215 const char *src_end; /* end ('\0') of source string */
215 const char *p_end; /* end ('\0') of pattern */ 216 const char *p_end; /* end ('\0') of pattern */
216 lua_State *L; 217 lua_State *L;
217 size_t nrep; /* limit to avoid non-linear complexity */ 218 lua_Unsigned nrep; /* limit to avoid non-linear complexity */
218 int matchdepth; /* control for recursive depth (to avoid C stack overflow) */ 219 int matchdepth; /* control for recursive depth (to avoid C stack overflow) */
219 int level; /* total number of captures (finished or unfinished) */ 220 unsigned char level; /* total number of captures (finished or unfinished) */
221 unsigned char usedlimit; /* true if real limit for 'nrep' was used */
220 struct { 222 struct {
221 const char *init; 223 const char *init;
222 ptrdiff_t len; 224 ptrdiff_t len;
@@ -235,13 +237,12 @@ static const char *match (MatchState *ms, const char *s, const char *p);
235 237
236 238
237/* 239/*
238** parameters to control the maximum number of operators handled in 240** Maximum number of operators handled in a match before consulting
239** a match (to avoid non-linear complexity). The maximum will be: 241** 'string.pattlimit'. (This lower limit is only to avoid wasting time
240** (subject length) * A_REPS + B_REPS 242** consulting 'string.pattlimit' in simple matches.)
241*/ 243*/
242#if !defined(A_REPS) 244#if !defined(PREPATTLIMIT)
243#define A_REPS 4 245#define PREPATTLIMIT 200
244#define B_REPS 100000
245#endif 246#endif
246 247
247 248
@@ -421,6 +422,27 @@ static const char *end_capture (MatchState *ms, const char *s,
421} 422}
422 423
423 424
425static void checklimit (MatchState *ms) {
426 lua_State *L = ms->L;
427 lua_assert(ms->nrep == 0);
428 if (!ms->usedlimit) { /* have not used 'string.pattlimit' yet? */
429 int top = lua_gettop(L);
430 if (lua_getglobal(L, "string") == LUA_TTABLE &&
431 lua_getfield(L, -1, "pattlimit") != LUA_TNIL) { /* is it defined? */
432 lua_Unsigned limit = (lua_Unsigned)lua_tointeger(L, -1); /* get it */
433 if (limit > PREPATTLIMIT) /* discount cycles already used */
434 ms->nrep = limit - PREPATTLIMIT;
435 ms->usedlimit = 1; /* do not use 'pattlimit' again */
436 }
437 else /* no limit defined; set no limit */
438 ms->nrep = ~(lua_Unsigned)0;
439 lua_settop(L, top); /* pop 'string' table and (maybe) 'pattlimit' */
440 }
441 if (ms->nrep == 0)
442 luaL_error(L, "pattern too complex");
443}
444
445
424static const char *match_capture (MatchState *ms, const char *s, int l) { 446static const char *match_capture (MatchState *ms, const char *s, int l) {
425 size_t len; 447 size_t len;
426 l = check_capture(ms, l); 448 l = check_capture(ms, l);
@@ -502,8 +524,8 @@ static const char *match (MatchState *ms, const char *s, const char *p) {
502 s = NULL; /* fail */ 524 s = NULL; /* fail */
503 } 525 }
504 else { /* matched once */ 526 else { /* matched once */
505 if (ms->nrep-- == 0) 527 if (--ms->nrep == 0)
506 luaL_error(ms->L, "pattern too complex"); 528 checklimit(ms);
507 switch (*ep) { /* handle optional suffix */ 529 switch (*ep) { /* handle optional suffix */
508 case '?': { /* optional */ 530 case '?': { /* optional */
509 const char *res; 531 const char *res;
@@ -607,10 +629,8 @@ static void prepstate (MatchState *ms, lua_State *L,
607 ms->src_init = s; 629 ms->src_init = s;
608 ms->src_end = s + ls; 630 ms->src_end = s + ls;
609 ms->p_end = p + lp; 631 ms->p_end = p + lp;
610 if (ls < (MAX_SIZET - B_REPS) / A_REPS) 632 ms->nrep = PREPATTLIMIT;
611 ms->nrep = A_REPS * ls + B_REPS; 633 ms->usedlimit = 0;
612 else /* overflow (very long subject) */
613 ms->nrep = MAX_SIZET; /* no limit */
614} 634}
615 635
616 636