Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size

[Paolo Bonzini <pbonzini@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.
> 
>