Re: [Qemu-devel] [PATCH for-1.2 v3 2/3] json-parser: don't replicate tokens at each level of recursion

[Eric Blake <eblake@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 2417 bytes --]

On 08/15/2012 12:45 PM, Michael Roth wrote:
> Currently, when parsing a stream of tokens we make a copy of the token
> list at the beginning of each level of recursion so that we do not
> modify the original list in cases where we need to fall back to an
> earlier state.
> 
> In the worst case, we will only read 1 or 2 tokens off the list before
> recursing again, which means an upper bound of roughly N^2 token allocations.
> 
> For a "reasonably" sized QMP request (in this a QMP representation of
> cirrus_vga's device state, generated via QIDL, being passed in via
> qom-set), this caused my 16GB's of memory to be exhausted before any
> noticeable progress was made by the parser.
> 
> This patch works around the issue by using single copy of the token list
> in the form of an indexable array so that we can save/restore state by
> manipulating indices.
> 
> A subsequent commit adds a "large_dict" test case which exhibits the
> same behavior as above. With this patch applied the test case successfully
> completes in under a second.
> 
> Tested with valgrind, make check, and QMP.
> 
> Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
> ---
>  json-parser.c |  230 +++++++++++++++++++++++++++++++++++----------------------
>  1 file changed, 142 insertions(+), 88 deletions(-)

I'm not the most familiar with this code, so take my review with a grain
of salt, but I read through it and the transformation looks sane (and my
non-code findings from v2 were fixed).

Reviewed-by: Eric Blake <eblake@redhat.com>

> +static JSONParserContext parser_context_save(JSONParserContext *ctxt)
> +{
> +    JSONParserContext saved_ctxt = {0};
> +    saved_ctxt.tokens.pos = ctxt->tokens.pos;
> +    saved_ctxt.tokens.count = ctxt->tokens.count;
> +    saved_ctxt.tokens.buf = ctxt->tokens.buf;

Is it any simpler to condense 3 lines to 1:

saved_cts.tokens = ctxt->tokens;

> +    return saved_ctxt;
> +}
> +
> +static void parser_context_restore(JSONParserContext *ctxt,
> +                                   JSONParserContext saved_ctxt)
> +{
> +    ctxt->tokens.pos = saved_ctxt.tokens.pos;
> +    ctxt->tokens.count = saved_ctxt.tokens.count;
> +    ctxt->tokens.buf = saved_ctxt.tokens.buf;

and again, ctxt->tokens = saved_ctxt.tokens;

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 620 bytes --]