Re: [Qemu-devel] [PATCH 4/4] json-streamer: Limit number of tokens in addition to total size

[Eric Blake]

On 10/29/2015 06:44 AM, Markus Armbruster wrote:
> Commit 29c75dd "json-streamer: limit the maximum recursion depth and
> maximum token count" attempts to guard against excessive heap usage by
> limiting total token size (it says "token count", but that's a lie).
> 
> Total token size is a rather imprecise predictor of heap usage: many
> small tokens use more space than few large tokens with the same input
> size, because there's a constant per-token overhead.
> 
> Tighten this up: limit the token count to 128Ki.
> 
> If you think 128Ki is too stingy: check-qjson's large_dict test eats a
> sweet 500MiB and pegs a core for four minutes on my machine to parse
> ~100K tokens.  Absurdly wasteful.

Sounds like we have some quadratic (or worse) scaling in the parser.
Worth fixing some day, but I also agree that we don't have to tackle it
in this series.

I'm assuming you temporarily patched check-qjson to use larger constants
when you hit your ~100K token testing?  Because I am definitely seeing a
lot of execution time spent on large_dict when running tests/check-qjson
by hand, in relation to all the other tests of that file, but not
minutes worth.  Care to post the diff you played with?

> 
> Signed-off-by: Markus Armbruster <address@hidden>
> ---
>  qobject/json-streamer.c | 2 ++
>  1 file changed, 2 insertions(+)

Reviewed-by: Eric Blake <address@hidden>

> 
> diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
> index 755c74d..df2b4c1 100644
> --- a/qobject/json-streamer.c
> +++ b/qobject/json-streamer.c
> @@ -19,6 +19,7 @@
>  #include "qapi/qmp/json-streamer.h"
>  
>  #define MAX_TOKEN_SIZE (64ULL << 20)
> +#define MAX_TOKEN_COUNT (128ULL << 10)
>  #define MAX_NESTING (1ULL << 10)
>  
>  static void json_message_process_token(JSONLexer *lexer, QString *token, 
> JSONTokenType type, int x, int y)
> @@ -64,6 +65,7 @@ static void json_message_process_token(JSONLexer *lexer, 
> QString *token, JSONTok
>           parser->bracket_count == 0)) {
>          goto out_emit;
>      } else if (parser->token_size > MAX_TOKEN_SIZE ||
> +               qlist_size(parser->tokens) > MAX_TOKEN_COUNT ||
>                 parser->bracket_count + parser->brace_count > MAX_NESTING) {
>          /* Security consideration, we limit total memory allocated per object
>           * and the maximum recursion depth that a message can force.
> 

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature