[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in
From: |
Paolo Bonzini |
Subject: |
Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size |
Date: |
Fri, 20 Nov 2015 09:50:43 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 |
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.
>
>
- [Qemu-devel] [PATCH v2 0/4] json-streamer: Fix up code to limit nesting and size, Markus Armbruster, 2015/11/19
- [Qemu-devel] [PATCH v2 3/4] check-qjson: Add test for JSON nesting depth limit, Markus Armbruster, 2015/11/19
- [Qemu-devel] [PATCH v2 2/4] json-streamer: Don't crash when input exceeds nesting limit, Markus Armbruster, 2015/11/19
- [Qemu-devel] [PATCH v2 1/4] json-streamer: Apply nesting limit more sanely, Markus Armbruster, 2015/11/19
- [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size, Markus Armbruster, 2015/11/19
- Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size, Paolo Bonzini, 2015/11/19
- Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size, Markus Armbruster, 2015/11/20
- Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size,
Paolo Bonzini <=
- Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size, Eric Blake, 2015/11/20
- Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size, Paolo Bonzini, 2015/11/23
- Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size, Eric Blake, 2015/11/23
- Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size, Markus Armbruster, 2015/11/23
Re: [Qemu-devel] [PATCH v2 0/4] json-streamer: Fix up code to limit nesting and size, Eric Blake, 2015/11/19