From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:59016) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZzhPT-00020l-S0 for qemu-devel@nongnu.org; Fri, 20 Nov 2015 03:51:12 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZzhPP-0002Iz-RP for qemu-devel@nongnu.org; Fri, 20 Nov 2015 03:51:11 -0500 Received: from mail-wm0-x22b.google.com ([2a00:1450:400c:c09::22b]:34819) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZzhPP-0002Iq-KS for qemu-devel@nongnu.org; Fri, 20 Nov 2015 03:51:07 -0500 Received: by wmdw130 with SMTP id w130so10791693wmd.0 for ; Fri, 20 Nov 2015 00:51:07 -0800 (PST) Sender: Paolo Bonzini References: <1447946948-12489-1-git-send-email-armbru@redhat.com> <1447946948-12489-5-git-send-email-armbru@redhat.com> <564E46AD.4030901@redhat.com> <87egflqjty.fsf@blackfin.pond.sub.org> From: Paolo Bonzini Message-ID: <564EDEE3.80000@redhat.com> Date: Fri, 20 Nov 2015 09:50:43 +0100 MIME-Version: 1.0 In-Reply-To: <87egflqjty.fsf@blackfin.pond.sub.org> Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 8bit Subject: Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Markus Armbruster Cc: qemu-devel@nongnu.org, lcapitulino@redhat.com On 20/11/2015 07:13, Markus Armbruster wrote: >>> @@ -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 || >> >> This is O(n^2). I'd rather skip this patch, fix the memory hog and >> possibly decrease MAX_TOKEN_SIZE a bit. > > I can't see the square right now. It's hidden in qlist_size: static void qlist_size_iter(QObject *obj, void *opaque) { size_t *count = opaque; (*count)++; } size_t qlist_size(const QList *qlist) { size_t count = 0; qlist_iter(qlist, qlist_size_iter, &count); return count; } You process the whole list on every token, which makes it O(n^2) where n is the token count. Paolo Anyway, O() is unchanged by my patch, > only n is more limited. See also commit 65c0f1e, which claims to have > fixed the quadradic behavior. > > Regardless, the memory consumption is still ridiculous, and we certainly > need to fix that. Whether we can have one for 2.5 I don't know. > > Even with a fix, this patch has some value. As explained in the commit > message, "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." As > long as we limit input to limit memory use, we better use a limit that's > connected to actual memory use with reasonable accuracy This patch > improves accuracy. > >>> 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. > >