webmcp

changeset 181:c2e76617c26c

Support 715827883 nested levels in JSON parser
author jbe
date Sat Aug 02 02:38:18 2014 +0200 (2014-08-02)
parents 887b77f71e5e
children b460ae08dd78
files libraries/json/json.c
line diff
     1.1 --- a/libraries/json/json.c	Sat Aug 02 00:39:41 2014 +0200
     1.2 +++ b/libraries/json/json.c	Sat Aug 02 02:38:18 2014 +0200
     1.3 @@ -5,14 +5,10 @@
     1.4  #include <math.h>
     1.5  
     1.6  // maximum number of nested JSON values (objects and arrays):
     1.7 -// NOTE: The Lua reference states that the stack may typically contain at least
     1.8 -//       "a few thousand elements". Since every nested level consumes
     1.9 -//       3 elements on the Lua stack (the object/array, its shadow table,
    1.10 -//       a string key or a placeholder), we limit the number of nested levels
    1.11 -//       to 500. If a stack overflow would still happen in the import function,
    1.12 -//       this is detected nevertheless and an error is thrown (instead of
    1.13 -//       returning nil and an error string).
    1.14 -#define JSON_MAXDEPTH 500
    1.15 +// NOTE: json_import can store (2^31-1) / 3 levels on stack swap;
    1.16 +//       one additional level is kept on the Lua stack, resulting
    1.17 +//       in 715827883 possible nested levels.
    1.18 +#define JSON_MAXDEPTH 715827883
    1.19  // NOTE: As long as the function json_export_internal is implemented
    1.20  //       recursively, JSON_MAXDEPTH needs to be low (e.g. 50) to avoid C stack
    1.21  //       overflows.
    1.22 @@ -195,6 +191,7 @@
    1.23  #define json_import_objectmt_idx 2
    1.24  #define json_import_arraymt_idx 3
    1.25  #define json_import_shadowtbl_idx 4
    1.26 +#define json_import_stackswap_idx 5
    1.27  
    1.28  // macros for hex decoding:
    1.29  #define json_utf16_surrogate(x) ((x) >= 0xD800 && (x) <= 0xDFFF)
    1.30 @@ -216,19 +213,20 @@
    1.31  
    1.32  // decodes a JSON document:
    1.33  static int json_import(lua_State *L) {
    1.34 -  int i;             // loop variable
    1.35 -  const char *str;   // string to parse
    1.36 -  size_t total;      // total length of string to parse
    1.37 -  size_t pos = 0;    // current position in string to parse
    1.38 -  size_t level = 0;  // nested levels of objects/arrays currently being processed
    1.39 +  int stackswapidx = 0;  // elements in stack swap table
    1.40 +  int i;                 // loop variable
    1.41 +  const char *str;       // string to parse
    1.42 +  size_t total;          // total length of string to parse
    1.43 +  size_t pos = 0;        // current position in string to parse
    1.44 +  size_t level = 0;      // nested levels of objects/arrays currently being processed
    1.45    int mode = JSON_STATE_VALUE;  // state of parser (i.e. "what's expected next?")
    1.46 -  unsigned char c;     // variable to store a single character to be processed (unsigned!)
    1.47 -  luaL_Buffer luabuf;  // Lua buffer to decode JSON string values
    1.48 -  char *cbuf;          // C buffer to decode JSON string values
    1.49 -  size_t outlen;       // maximum length or write position of C buffer
    1.50 -  long codepoint;      // decoded UTF-16 character or higher codepoint
    1.51 -  long utf16tail;      // second decoded UTF-16 character (surrogate tail)
    1.52 -  size_t arraylen;     // variable to temporarily store the array length
    1.53 +  unsigned char c;       // variable to store a single character to be processed (unsigned!)
    1.54 +  luaL_Buffer luabuf;    // Lua buffer to decode JSON string values
    1.55 +  char *cbuf;            // C buffer to decode JSON string values
    1.56 +  size_t outlen;         // maximum length or write position of C buffer
    1.57 +  long codepoint;        // decoded UTF-16 character or higher codepoint
    1.58 +  long utf16tail;        // second decoded UTF-16 character (surrogate tail)
    1.59 +  size_t arraylen;       // variable to temporarily store the array length
    1.60    // require string as argument and convert to C string with length information:
    1.61    str = luaL_checklstring(L, 1, &total);
    1.62    // if string contains a NULL byte, this is a syntax error
    1.63 @@ -241,6 +239,9 @@
    1.64    json_regfetch(L, arraymt);
    1.65    // push shadowtbl onto stack position 4:
    1.66    json_regfetch(L, shadowtbl);
    1.67 +  // push table for stack swapping onto stack position 5:
    1.68 +  // (needed to avoid Lua stack overflows)
    1.69 +  lua_newtable(L);
    1.70    // main loop of parser:
    1.71    json_import_loop:
    1.72    // skip whitespace and store next character in variable 'c':
    1.73 @@ -269,18 +270,44 @@
    1.74        lua_pushliteral(L, "Unexpected end of JSON document");
    1.75      }
    1.76      return 2;
    1.77 -  // new JSON object:
    1.78 +  // new JSON object or JSON array:
    1.79    case '{':
    1.80 -    // if a JSON object is not expected here, then return an error:
    1.81 +  case '[':
    1.82 +    // if an encountered JSON object is not expected here, then return an error:
    1.83      if (
    1.84 +      c == '{' &&
    1.85 +      mode != JSON_STATE_VALUE &&
    1.86 +      mode != JSON_STATE_OBJECT_VALUE &&
    1.87 +      mode != JSON_STATE_ARRAY_VALUE
    1.88 +    ) goto json_import_syntax_error;
    1.89 +    // if an encountered JSON array is not expected here, then return an error:
    1.90 +    if (
    1.91 +      c == '[' &&
    1.92        mode != JSON_STATE_VALUE &&
    1.93        mode != JSON_STATE_OBJECT_VALUE &&
    1.94        mode != JSON_STATE_ARRAY_VALUE
    1.95      ) goto json_import_syntax_error;
    1.96 -    // create JSON object on stack:
    1.97 +    // consume input character:
    1.98 +    pos++;
    1.99 +    // limit nested levels:
   1.100 +    if (level >= JSON_MAXDEPTH) {
   1.101 +      lua_pushnil(L);
   1.102 +      lua_pushfstring(L, "More than %d nested JSON levels", JSON_MAXDEPTH);
   1.103 +      return 2;
   1.104 +    }
   1.105 +    // swap Lua stack entries for previous level to swap table:
   1.106 +    // (avoids depth limitations due to Lua stack size)
   1.107 +    if (level) {
   1.108 +      lua_rawseti(L, json_import_stackswap_idx, ++stackswapidx);
   1.109 +      lua_rawseti(L, json_import_stackswap_idx, ++stackswapidx);
   1.110 +      lua_rawseti(L, json_import_stackswap_idx, ++stackswapidx);
   1.111 +    }
   1.112 +    // increment level:
   1.113 +    level++;
   1.114 +    // create JSON object or JSON array on stack:
   1.115      lua_newtable(L);
   1.116 -    // set metatable of JSON object:
   1.117 -    lua_pushvalue(L, json_import_objectmt_idx);
   1.118 +    // set metatable of JSON object or JSON array:
   1.119 +    lua_pushvalue(L, c == '{' ? json_import_objectmt_idx : json_import_arraymt_idx);
   1.120      lua_setmetatable(L, -2);
   1.121      // create internal shadow table on stack:
   1.122      lua_newtable(L);
   1.123 @@ -288,49 +315,18 @@
   1.124      lua_pushvalue(L, -2);
   1.125      lua_pushvalue(L, -2);
   1.126      lua_rawset(L, json_import_shadowtbl_idx);
   1.127 -    // expect object key (or end of object) to follow:
   1.128 -    mode = JSON_STATE_OBJECT_KEY;
   1.129 -    // jump to common code for opening JSON object and JSON array:
   1.130 -    goto json_import_open;
   1.131 -  // new JSON array:
   1.132 -  case '[':
   1.133 -    // if a JSON array is not expected here, then return an error:
   1.134 -    if (
   1.135 -      mode != JSON_STATE_VALUE &&
   1.136 -      mode != JSON_STATE_OBJECT_VALUE &&
   1.137 -      mode != JSON_STATE_ARRAY_VALUE
   1.138 -    ) goto json_import_syntax_error;
   1.139 -    // create JSON array on stack:
   1.140 -    lua_newtable(L);
   1.141 -    // set metatable of JSON array:
   1.142 -    lua_pushvalue(L, json_import_arraymt_idx);
   1.143 -    lua_setmetatable(L, -2);
   1.144 -    // create internal shadow table on stack:
   1.145 -    lua_newtable(L);
   1.146 -    // register internal shadow table:
   1.147 -    lua_pushvalue(L, -2);
   1.148 -    lua_pushvalue(L, -2);
   1.149 -    lua_rawset(L, json_import_shadowtbl_idx);
   1.150 -    // add nil as key (needed to keep stack balance) and as magic to detect arrays:
   1.151 -    lua_pushnil(L);
   1.152 -    // expect array value (or end of array) to follow:
   1.153 -    mode = JSON_STATE_ARRAY_VALUE;
   1.154 -    // continue with common code for opening JSON object and JSON array:
   1.155 -  // common code for opening JSON object or JSON array:
   1.156 -  json_import_open:
   1.157 -    // limit nested levels:
   1.158 -    if (level >= JSON_MAXDEPTH) {
   1.159 -      lua_pushnil(L);
   1.160 -      lua_pushfstring(L, "More than %d nested JSON levels", JSON_MAXDEPTH);
   1.161 -      return 2;
   1.162 +    // distinguish between JSON objects and JSON arrays:
   1.163 +    if (c == '{') {
   1.164 +      // if JSON object,
   1.165 +      // expect object key (or end of object) to follow:
   1.166 +      mode = JSON_STATE_OBJECT_KEY;
   1.167 +    } else {
   1.168 +      // if JSON array,
   1.169 +      // expect array value (or end of array) to follow:
   1.170 +      mode = JSON_STATE_ARRAY_VALUE;
   1.171 +      // add nil as key (needed to keep stack balance) and as magic to detect arrays:
   1.172 +      if (c == '[') lua_pushnil(L);
   1.173      }
   1.174 -    // additional buffer overflow protection:
   1.175 -    if (!lua_checkstack(L, LUA_MINSTACK))
   1.176 -      return luaL_error(L, "Caught stack overflow in JSON import function (too many nested levels and stack size too small)");
   1.177 -    // increment level:
   1.178 -    level++;
   1.179 -    // consume input character:
   1.180 -    pos++;
   1.181      goto json_import_loop;
   1.182    // end of JSON object:
   1.183    case '}':
   1.184 @@ -360,6 +356,13 @@
   1.185      // check if nested:
   1.186      if (--level) {
   1.187        // if nested,
   1.188 +      // restore previous stack elements from stack swap:
   1.189 +      lua_rawgeti(L, json_import_stackswap_idx, stackswapidx--);
   1.190 +      lua_insert(L, -2);
   1.191 +      lua_rawgeti(L, json_import_stackswap_idx, stackswapidx--);
   1.192 +      lua_insert(L, -2);
   1.193 +      lua_rawgeti(L, json_import_stackswap_idx, stackswapidx--);
   1.194 +      lua_insert(L, -2);
   1.195        // check if outer(!) structure is an array or object:
   1.196        if (lua_isnil(L, -2)) {
   1.197          // select array value processing:

Impressum / About Us