tree 12affa14eb4cb53f2cf8bd0ffaebc0c325b14f65
parent a86a4c2f7b7f0b72816ea1c219d8140699b6665b
author Michael Roth <mdroth@linux.vnet.ibm.com> 1345056343 -0500
committer Anthony Liguori <aliguori@us.ibm.com> 1345142475 -0500

json-parser: don't replicate tokens at each level of recursion

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.

Reviewed-by: Eric Blake <eblake@redhat.com>
Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>