2016-10-26 23:05 GMT+03:00 Dominique Pellé <[email protected]>: > Christian Brabandt <[email protected]> wrote: > >> On Mi, 26 Okt 2016, LCD 47 wrote: >> >>> * There is even a segfault: >>> >>> json_decode(repeat('[', 100000)) " segfault >>> >> >> Oh, that one is nasty. I just made a backtrace: >> #0 0x00007ffff4d0bbab in _int_malloc (av=av@entry=0x7ffff502bb00 >> <main_arena>, bytes=bytes@entry=88) at malloc.c:3384 >> #1 0x00007ffff4d0dd94 in __GI___libc_malloc (bytes=88) at malloc.c:2925 >> #2 0x00000000004ea63a in lalloc (size=88, message=1) at misc2.c:942 >> #3 0x00000000004ea565 in alloc_clear (size=88) at misc2.c:864 >> #4 0x00000000004c3dff in list_alloc () at list.c:75 >> #5 0x00000000004c3e62 in rettv_list_alloc (rettv=0x7fffff7ff230) at >> list.c:95 >> #6 0x000000000060c9e6 in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff230, options=0) at json.c:388 >> #7 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff230, options=0) at json.c:732 >> #8 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff2f0, options=0) at json.c:408 >> #9 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff2f0, options=0) at json.c:732 >> #10 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff3b0, options=0) at json.c:408 >> #11 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff3b0, options=0) at json.c:732 >> #12 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff470, options=0) at json.c:408 >> #13 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff470, options=0) at json.c:732 >> #14 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff530, options=0) at json.c:408 >> #15 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff530, options=0) at json.c:732 >> #16 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff5f0, options=0) at json.c:408 >> #17 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff5f0, options=0) at json.c:732 >> #18 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff6b0, options=0) at json.c:408 >> #19 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff6b0, options=0) at json.c:732 >> #20 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff770, options=0) at json.c:408 >> #21 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff770, options=0) at json.c:732 >> #22 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff830, options=0) at json.c:408 >> #23 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff830, options=0) at json.c:732 >> #24 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff8f0, options=0) at json.c:408 >> #25 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff8f0, options=0) at json.c:732 >> #26 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ff9b0, options=0) at json.c:408 >> #27 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ff9b0, options=0) at json.c:732 >> #28 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ffa70, options=0) at json.c:408 >> #29 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ffa70, options=0) at json.c:732 >> #30 0x000000000060ca9e in json_decode_array (reader=0x7fffffffd1b0, >> res=0x7fffff7ffb30, options=0) at json.c:408 >> #31 0x000000000060d692 in json_decode_item (reader=0x7fffffffd1b0, >> res=0x7fffff7ffb30, options=0) at json.c:732 >> >> and goes on until: >> (gdb) bt -1 >> #87314 0x000000000060e06b in main (argc=4, argv=0x7fffffffe2e8) at main.c:415 >> >> That looks like some kind of memory corruption, however neither valgrind >> nor asan return anything useful > > > It's a stack overflow caused by a deep recursivity. > > If we can reduce the stack usage of functions json_decode_array() > and json_decode_items(), then we can allow deeper recursivity. > But it will still crash if with enough [[[[[.... The only way to fix it > would be to avoid recursive calls, but is it worth making it more > complex for such unlikely edge cases?
Non-recursive JSON parser was already written, and it was done more then once. Specifically Neovim’s non-recursive JSON parser is a “port” (mostly the structure of the code, also prevented me from introducing some bugs) of some javascript parser: apparently people there saw some point in preventing stack overflows and it is not the only part of Neovim which was (re)written by me to be non-recursive: why should I make intentionally bugged code if I can do the other way around? Also proper non-recursive implementation is faster. (As a side note: Neovim got its parser after Vim, not before, so Bram could be blamed for not porting JS library or porting/copying/writing some other non-recursive code, but could not be blamed for ignoring Neovim implementation.) Normally in Vim such problems are resolved by introducing some kind of global variable with “recursion depth” counter. Though given that evalN functions used to parse expressions and thus call json_decode are themselves recursive and, if I am not mistaking, function used to execute commands is also recursive I guess I could still write a code which will result in a stack overflow unless “recursion depth” limits will not be too low to produce problems in some real-world cases. > > gcc and clang have similar stack overflows when parsing C on edge > cases. I remember opening this old bug which causes gcc to crash with > many stars *** and it was not deemed worth fixing. See: > > http://www.mail-archive.com/[email protected]/msg208512.html > > 12 years after opening this ticket, I see that both clang and gcc still > crash when trying to compile the c file attached in above bug. > > Regards > Dominique > > -- > -- > You received this message from the "vim_dev" maillist. > Do not top-post! Type your reply below the text you are replying to. > For more information, visit http://www.vim.org/maillist.php > > --- > You received this message because you are subscribed to the Google Groups > "vim_dev" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/d/optout. -- -- You received this message from the "vim_dev" maillist. Do not top-post! Type your reply below the text you are replying to. For more information, visit http://www.vim.org/maillist.php --- You received this message because you are subscribed to the Google Groups "vim_dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
