From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from eggs.gnu.org ([208.118.235.92]:35045)
	by lists.gnu.org with esmtp (Exim 4.71)
	(envelope-from <flukshun@gmail.com>) id 1T16ts-0003ow-RC
	for qemu-devel@nongnu.org; Mon, 13 Aug 2012 22:30:33 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <flukshun@gmail.com>) id 1T16tr-0005Pj-Km
	for qemu-devel@nongnu.org; Mon, 13 Aug 2012 22:30:32 -0400
Received: from mail-ob0-f173.google.com ([209.85.214.173]:54360)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <flukshun@gmail.com>) id 1T16tr-0005Pf-FE
	for qemu-devel@nongnu.org; Mon, 13 Aug 2012 22:30:31 -0400
Received: by obbta14 with SMTP id ta14so7408626obb.4
	for <qemu-devel@nongnu.org>; Mon, 13 Aug 2012 19:30:31 -0700 (PDT)
Sender: fluxion <flukshun@gmail.com>
Date: Mon, 13 Aug 2012 21:30:06 -0500
From: Michael Roth <mdroth@linux.vnet.ibm.com>
Message-ID: <20120814023006.GF16157@illuin>
References: <1344641050-21997-1-git-send-email-mdroth@linux.vnet.ibm.com>
	<87lihibpah.fsf@blackfin.pond.sub.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <87lihibpah.fsf@blackfin.pond.sub.org>
Subject: Re: [Qemu-devel] [PATCH] json-parser: don't replicate tokens
	at	each level of recursion
List-Id: <qemu-devel.nongnu.org>
List-Unsubscribe: <https://lists.nongnu.org/mailman/options/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=unsubscribe>
List-Archive: <http://lists.nongnu.org/archive/html/qemu-devel>
List-Post: <mailto:qemu-devel@nongnu.org>
List-Help: <mailto:qemu-devel-request@nongnu.org?subject=help>
List-Subscribe: <https://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=subscribe>
To: Markus Armbruster <armbru@redhat.com>
Cc: aliguori@us.ibm.com, qemu-devel@nongnu.org, lcapitulino@redhat.com

On Mon, Aug 13, 2012 at 08:49:26PM +0200, Markus Armbruster wrote:
> Michael Roth <mdroth@linux.vnet.ibm.com> writes:
> 
> > 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. The command is here for
> > reference, and can be issued against upstream QMP to reproduce (failure
> > occurs before any qmp command routing/execution):
> >
> > http://pastebin.com/mJrZ3Ctg
> 
> Commit messages are forever, pastebins aren't.
> 
> What about preserving your test case for eternity under tests/?

We might be able to generate some json objects that cause the behavior and add
them to check-qjson.

> 
> [...]
>