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.
>
>
