From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([208.118.235.92]:45696) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1T1jpp-0000sE-7W for qemu-devel@nongnu.org; Wed, 15 Aug 2012 16:04:58 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1T1jpo-0001XA-0o for qemu-devel@nongnu.org; Wed, 15 Aug 2012 16:04:57 -0400 Received: from mx1.redhat.com ([209.132.183.28]:36454) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1T1jpn-0001X6-P0 for qemu-devel@nongnu.org; Wed, 15 Aug 2012 16:04:55 -0400 Message-ID: <502C00E4.1020009@redhat.com> Date: Wed, 15 Aug 2012 14:04:52 -0600 From: Eric Blake MIME-Version: 1.0 References: <1345056344-31849-1-git-send-email-mdroth@linux.vnet.ibm.com> <1345056344-31849-2-git-send-email-mdroth@linux.vnet.ibm.com> In-Reply-To: <1345056344-31849-2-git-send-email-mdroth@linux.vnet.ibm.com> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="------------enigB4F8E67730BDE06C6600FF0C" Subject: Re: [Qemu-devel] [PATCH for-1.2 v3 2/3] json-parser: don't replicate tokens at each level of recursion List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Michael Roth Cc: armbru@redhat.com, aliguori@us.ibm.com, qemu-devel@nongnu.org, lcapitulino@redhat.com This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enigB4F8E67730BDE06C6600FF0C Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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. >=20 > 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 alloca= tions. >=20 > 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. >=20 > This patch works around the issue by using single copy of the token lis= t > in the form of an indexable array so that we can save/restore state by > manipulating indices. >=20 > A subsequent commit adds a "large_dict" test case which exhibits the > same behavior as above. With this patch applied the test case successfu= lly > completes in under a second. >=20 > Tested with valgrind, make check, and QMP. >=20 > Signed-off-by: Michael Roth > --- > 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 > +static JSONParserContext parser_context_save(JSONParserContext *ctxt) > +{ > + JSONParserContext saved_ctxt =3D {0}; > + saved_ctxt.tokens.pos =3D ctxt->tokens.pos; > + saved_ctxt.tokens.count =3D ctxt->tokens.count; > + saved_ctxt.tokens.buf =3D ctxt->tokens.buf; Is it any simpler to condense 3 lines to 1: saved_cts.tokens =3D ctxt->tokens; > + return saved_ctxt; > +} > + > +static void parser_context_restore(JSONParserContext *ctxt, > + JSONParserContext saved_ctxt) > +{ > + ctxt->tokens.pos =3D saved_ctxt.tokens.pos; > + ctxt->tokens.count =3D saved_ctxt.tokens.count; > + ctxt->tokens.buf =3D saved_ctxt.tokens.buf; and again, ctxt->tokens =3D saved_ctxt.tokens; --=20 Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --------------enigB4F8E67730BDE06C6600FF0C Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBCAAGBQJQLADkAAoJEKeha0olJ0NqcSQH/ilOvCN4OOMSr37O3KTjoI3M R1r4qjEZReu7aW3oQ1KZgSxGGyKh6wmRwT7kTYTLdrIht0Ol0cHcn1qTxiO8u+3Y yRM2eDUHoasDDuGbN475SGA6exFJ+/bupQwYunC2tNsd92101m3zfwciJv4XqyBA 8YQ64KGsIH6URx+GJ7l5ZvHavUUw7sNlPlVsl1PIi6q7sASIiV5C3NNQEdwcBKlz Q29LmzWrYzFxJ7F/rpIitbKiCsoXxp6z2KnxPDZiOl45Vm/OC9SSa3AlwUDcYJGb f6BS9k7Zbkbgjf48WY9XVI1KcWuubGV+IljTWPSM5snQ1ZTGxwXJ4PIYuJQYn9U= =68Fc -----END PGP SIGNATURE----- --------------enigB4F8E67730BDE06C6600FF0C--