[Qemu-devel] [PULL for-2.5 00/13] QMP and QObject patches

[Qemu-devel] [PULL for-2.5 00/13] QMP and QObject patches

[Markus Armbruster]

The following changes since commit 1a4dab849d5d06191ab5e5850f6b8bfcad8ceb47:

  Merge remote-tracking branch 'remotes/kevin/tags/for-upstream' into staging (2015-11-25 14:47:06 +0000)

are available in the git repository at:

  git://repo.or.cz/qemu/armbru.git tags/pull-monitor-2015-11-26

for you to fetch changes up to df649835fe48f635a93316fdefe96ced7189316e:

  qjson: Limit number of tokens in addition to total size (2015-11-26 10:07:07 +0100)

----------------------------------------------------------------
QMP and QObject patches

----------------------------------------------------------------
Markus Armbruster (10):
      monitor: Plug memory leak on QMP error
      qjson: Apply nesting limit more sanely
      qjson: Don't crash when input exceeds nesting limit
      check-qjson: Add test for JSON nesting depth limit
      qjson: Spell out some silent assumptions
      qjson: Give each of the six structural chars its own token type
      qjson: Inline token_is_keyword() and simplify
      qjson: Inline token_is_escape() and simplify
      qjson: Convert to parser to recursive descent
      qjson: Limit number of tokens in addition to total size

Paolo Bonzini (3):
      qjson: replace QString in JSONLexer with GString
      qjson: store tokens in a GQueue
      qjson: surprise, allocating 6 QObjects per token is expensive

 include/qapi/qmp/json-lexer.h    |  16 +-
 include/qapi/qmp/json-parser.h   |   4 +-
 include/qapi/qmp/json-streamer.h |  16 +-
 monitor.c                        |   3 +-
 qga/main.c                       |   2 +-
 qobject/json-lexer.c             |  48 +++---
 qobject/json-parser.c            | 330 ++++++++++++---------------------------
 qobject/json-streamer.c          |  89 ++++++-----
 qobject/qjson.c                  |   2 +-
 tests/check-qjson.c              |  25 +++
 tests/libqtest.c                 |   2 +-
 11 files changed, 224 insertions(+), 313 deletions(-)

-- 
2.4.3

[Qemu-devel] [PULL for-2.5 01/13] monitor: Plug memory leak on QMP error

[Markus Armbruster]

Leak introduced in commit 8a4f501..710aec9, v2.4.0.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Message-Id: <1446117309-15322-1-git-send-email-armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
Reviewed-by: Luiz Capitulino <lcapitulino@redhat.com>
---
 monitor.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/monitor.c b/monitor.c
index e4cf34e..49073ac 100644
--- a/monitor.c
+++ b/monitor.c
@@ -3907,6 +3907,7 @@ static void handle_qmp_command(JSONMessageParser *parser, QList *tokens)
 err_out:
     monitor_protocol_emitter(mon, data, local_err);
     qobject_decref(data);
+    error_free(local_err);
     QDECREF(input);
     QDECREF(args);
 }
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 02/13] qjson: Apply nesting limit more sanely

[Markus Armbruster]

The nesting limit from commit 29c75dd "json-streamer: limit the
maximum recursion depth and maximum token count" applies separately to
braces and brackets.  This makes no sense.  Apply it to their sum,
because that's actually a measure of recursion depth.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
Message-Id: <1448486613-17634-2-git-send-email-armbru@redhat.com>
---
 qobject/json-streamer.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index 1b2f9b1..dced2c7 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -64,8 +64,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 ||
-               parser->bracket_count > MAX_NESTING ||
-               parser->brace_count > MAX_NESTING) {
+               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.
          */
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 03/13] qjson: Don't crash when input exceeds nesting limit

[Markus Armbruster]

We limit nesting depth and input size to defend against input
triggering excessive heap or stack memory use (commit 29c75dd
json-streamer: limit the maximum recursion depth and maximum token
count).  However, when the nesting limit is exceeded,
parser_context_peek_token()'s assertion fails.

Broken in commit 65c0f1e "json-parser: don't replicate tokens at each
level of recursion".

To reproduce stuff 1025 open braces or brackets into QMP.

Fix by taking the error exit instead of the normal one.

Reported-by: Eric Blake <eblake@redhat.com>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
Message-Id: <1448486613-17634-3-git-send-email-armbru@redhat.com>
---
 qobject/json-streamer.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index dced2c7..2bd22a7 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -68,13 +68,14 @@ static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTok
         /* Security consideration, we limit total memory allocated per object
          * and the maximum recursion depth that a message can force.
          */
-        goto out_emit;
+        goto out_emit_bad;
     }
 
     return;
 
 out_emit_bad:
-    /* clear out token list and tell the parser to emit and error
+    /*
+     * Clear out token list and tell the parser to emit an error
      * indication by passing it a NULL list
      */
     QDECREF(parser->tokens);
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 04/13] check-qjson: Add test for JSON nesting depth limit

[Markus Armbruster]

This would have prevented the regression mentioned in the previous
commit.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
Message-Id: <1448486613-17634-4-git-send-email-armbru@redhat.com>
---
 tests/check-qjson.c | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

diff --git a/tests/check-qjson.c b/tests/check-qjson.c
index 1cfffa5..61e9bfb 100644
--- a/tests/check-qjson.c
+++ b/tests/check-qjson.c
@@ -1484,6 +1484,30 @@ static void unterminated_literal(void)
     g_assert(obj == NULL);
 }
 
+static char *make_nest(char *buf, size_t cnt)
+{
+    memset(buf, '[', cnt - 1);
+    buf[cnt - 1] = '{';
+    buf[cnt] = '}';
+    memset(buf + cnt + 1, ']', cnt - 1);
+    buf[2 * cnt] = 0;
+    return buf;
+}
+
+static void limits_nesting(void)
+{
+    enum { max_nesting = 1024 }; /* see qobject/json-streamer.c */
+    char buf[2 * (max_nesting + 1) + 1];
+    QObject *obj;
+
+    obj = qobject_from_json(make_nest(buf, max_nesting));
+    g_assert(obj != NULL);
+    qobject_decref(obj);
+
+    obj = qobject_from_json(make_nest(buf, max_nesting + 1));
+    g_assert(obj == NULL);
+}
+
 int main(int argc, char **argv)
 {
     g_test_init(&argc, &argv, NULL);
@@ -1519,6 +1543,7 @@ int main(int argc, char **argv)
     g_test_add_func("/errors/invalid_array_comma", invalid_array_comma);
     g_test_add_func("/errors/invalid_dict_comma", invalid_dict_comma);
     g_test_add_func("/errors/unterminated/literal", unterminated_literal);
+    g_test_add_func("/errors/limits/nesting", limits_nesting);
 
     return g_test_run();
 }
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 05/13] qjson: Spell out some silent assumptions

[Markus Armbruster]

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Message-Id: <1448486613-17634-5-git-send-email-armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 include/qapi/qmp/json-lexer.h | 3 ++-
 qobject/json-lexer.c          | 7 ++++++-
 2 files changed, 8 insertions(+), 2 deletions(-)

diff --git a/include/qapi/qmp/json-lexer.h b/include/qapi/qmp/json-lexer.h
index cdff046..61a143f 100644
--- a/include/qapi/qmp/json-lexer.h
+++ b/include/qapi/qmp/json-lexer.h
@@ -18,7 +18,8 @@
 #include "qapi/qmp/qlist.h"
 
 typedef enum json_token_type {
-    JSON_OPERATOR = 100,
+    JSON_MIN = 100,
+    JSON_OPERATOR = JSON_MIN,
     JSON_INTEGER,
     JSON_FLOAT,
     JSON_KEYWORD,
diff --git a/qobject/json-lexer.c b/qobject/json-lexer.c
index b19623e..5735c1e 100644
--- a/qobject/json-lexer.c
+++ b/qobject/json-lexer.c
@@ -30,7 +30,7 @@
  */
 
 enum json_lexer_state {
-    IN_ERROR = 0,
+    IN_ERROR = 0,               /* must really be 0, see json_lexer[] */
     IN_DQ_UCODE3,
     IN_DQ_UCODE2,
     IN_DQ_UCODE1,
@@ -62,6 +62,8 @@ enum json_lexer_state {
     IN_START,
 };
 
+QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START);
+
 #define TERMINAL(state) [0 ... 0x7F] = (state)
 
 /* Return whether TERMINAL is a terminal state and the transition to it
@@ -71,6 +73,8 @@ enum json_lexer_state {
             (json_lexer[(old_state)][0] == (terminal))
 
 static const uint8_t json_lexer[][256] =  {
+    /* Relies on default initialization to IN_ERROR! */
+
     /* double quote string */
     [IN_DQ_UCODE3] = {
         ['0' ... '9'] = IN_DQ_STRING,
@@ -287,6 +291,7 @@ static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
     }
 
     do {
+        assert(lexer->state <= ARRAY_SIZE(json_lexer));
         new_state = json_lexer[lexer->state][(uint8_t)ch];
         char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state);
         if (char_consumed) {
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 06/13] qjson: Give each of the six structural chars its own token type

[Markus Armbruster]

Simplifies things, because we always check for a specific one.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Message-Id: <1448486613-17634-6-git-send-email-armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 include/qapi/qmp/json-lexer.h |  7 ++++++-
 qobject/json-lexer.c          | 19 ++++++++++++-------
 qobject/json-parser.c         | 31 +++++++++----------------------
 qobject/json-streamer.c       | 32 +++++++++++++++-----------------
 4 files changed, 42 insertions(+), 47 deletions(-)

diff --git a/include/qapi/qmp/json-lexer.h b/include/qapi/qmp/json-lexer.h
index 61a143f..f3e8dc7 100644
--- a/include/qapi/qmp/json-lexer.h
+++ b/include/qapi/qmp/json-lexer.h
@@ -19,7 +19,12 @@
 
 typedef enum json_token_type {
     JSON_MIN = 100,
-    JSON_OPERATOR = JSON_MIN,
+    JSON_LCURLY = JSON_MIN,
+    JSON_RCURLY,
+    JSON_LSQUARE,
+    JSON_RSQUARE,
+    JSON_COLON,
+    JSON_COMMA,
     JSON_INTEGER,
     JSON_FLOAT,
     JSON_KEYWORD,
diff --git a/qobject/json-lexer.c b/qobject/json-lexer.c
index 5735c1e..1df7d5e 100644
--- a/qobject/json-lexer.c
+++ b/qobject/json-lexer.c
@@ -257,12 +257,12 @@ static const uint8_t json_lexer[][256] =  {
         ['0'] = IN_ZERO,
         ['1' ... '9'] = IN_NONZERO_NUMBER,
         ['-'] = IN_NEG_NONZERO_NUMBER,
-        ['{'] = JSON_OPERATOR,
-        ['}'] = JSON_OPERATOR,
-        ['['] = JSON_OPERATOR,
-        [']'] = JSON_OPERATOR,
-        [','] = JSON_OPERATOR,
-        [':'] = JSON_OPERATOR,
+        ['{'] = JSON_LCURLY,
+        ['}'] = JSON_RCURLY,
+        ['['] = JSON_LSQUARE,
+        [']'] = JSON_RSQUARE,
+        [','] = JSON_COMMA,
+        [':'] = JSON_COLON,
         ['a' ... 'z'] = IN_KEYWORD,
         ['%'] = IN_ESCAPE,
         [' '] = IN_WHITESPACE,
@@ -299,7 +299,12 @@ static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
         }
 
         switch (new_state) {
-        case JSON_OPERATOR:
+        case JSON_LCURLY:
+        case JSON_RCURLY:
+        case JSON_LSQUARE:
+        case JSON_RSQUARE:
+        case JSON_COLON:
+        case JSON_COMMA:
         case JSON_ESCAPE:
         case JSON_INTEGER:
         case JSON_FLOAT:
diff --git a/qobject/json-parser.c b/qobject/json-parser.c
index ac991ba..020c6e1 100644
--- a/qobject/json-parser.c
+++ b/qobject/json-parser.c
@@ -63,19 +63,6 @@ static JSONTokenType token_get_type(QObject *obj)
     return qdict_get_int(qobject_to_qdict(obj), "type");
 }
 
-static int token_is_operator(QObject *obj, char op)
-{
-    const char *val;
-
-    if (token_get_type(obj) != JSON_OPERATOR) {
-        return 0;
-    }
-
-    val = token_get_value(obj);
-
-    return (val[0] == op) && (val[1] == 0);
-}
-
 static int token_is_keyword(QObject *obj, const char *value)
 {
     if (token_get_type(obj) != JSON_KEYWORD) {
@@ -384,7 +371,7 @@ static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
         goto out;
     }
 
-    if (!token_is_operator(token, ':')) {
+    if (token_get_type(token) != JSON_COLON) {
         parse_error(ctxt, token, "missing : in object pair");
         goto out;
     }
@@ -419,7 +406,7 @@ static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
         goto out;
     }
 
-    if (!token_is_operator(token, '{')) {
+    if (token_get_type(token) != JSON_LCURLY) {
         goto out;
     }
 
@@ -431,7 +418,7 @@ static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
         goto out;
     }
 
-    if (!token_is_operator(peek, '}')) {
+    if (token_get_type(peek) != JSON_RCURLY) {
         if (parse_pair(ctxt, dict, ap) == -1) {
             goto out;
         }
@@ -442,8 +429,8 @@ static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
             goto out;
         }
 
-        while (!token_is_operator(token, '}')) {
-            if (!token_is_operator(token, ',')) {
+        while (token_get_type(token) != JSON_RCURLY) {
+            if (token_get_type(token) != JSON_COMMA) {
                 parse_error(ctxt, token, "expected separator in dict");
                 goto out;
             }
@@ -481,7 +468,7 @@ static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
         goto out;
     }
 
-    if (!token_is_operator(token, '[')) {
+    if (token_get_type(token) != JSON_LSQUARE) {
         goto out;
     }
 
@@ -493,7 +480,7 @@ static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
         goto out;
     }
 
-    if (!token_is_operator(peek, ']')) {
+    if (token_get_type(peek) != JSON_RSQUARE) {
         QObject *obj;
 
         obj = parse_value(ctxt, ap);
@@ -510,8 +497,8 @@ static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
             goto out;
         }
 
-        while (!token_is_operator(token, ']')) {
-            if (!token_is_operator(token, ',')) {
+        while (token_get_type(token) != JSON_RSQUARE) {
+            if (token_get_type(token) != JSON_COMMA) {
                 parse_error(ctxt, token, "expected separator in list");
                 goto out;
             }
diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index 2bd22a7..4a161a1 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -26,23 +26,21 @@ static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTok
     JSONMessageParser *parser = container_of(lexer, JSONMessageParser, lexer);
     QDict *dict;
 
-    if (type == JSON_OPERATOR) {
-        switch (qstring_get_str(token)[0]) {
-        case '{':
-            parser->brace_count++;
-            break;
-        case '}':
-            parser->brace_count--;
-            break;
-        case '[':
-            parser->bracket_count++;
-            break;
-        case ']':
-            parser->bracket_count--;
-            break;
-        default:
-            break;
-        }
+    switch (type) {
+    case JSON_LCURLY:
+        parser->brace_count++;
+        break;
+    case JSON_RCURLY:
+        parser->brace_count--;
+        break;
+    case JSON_LSQUARE:
+        parser->bracket_count++;
+        break;
+    case JSON_RSQUARE:
+        parser->bracket_count--;
+        break;
+    default:
+        break;
     }
 
     dict = qdict_new();
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 07/13] qjson: Inline token_is_keyword() and simplify

[Markus Armbruster]

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Message-Id: <1448486613-17634-7-git-send-email-armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 qobject/json-parser.c | 20 +++++++-------------
 1 file changed, 7 insertions(+), 13 deletions(-)

diff --git a/qobject/json-parser.c b/qobject/json-parser.c
index 020c6e1..df76cc3 100644
--- a/qobject/json-parser.c
+++ b/qobject/json-parser.c
@@ -63,15 +63,6 @@ static JSONTokenType token_get_type(QObject *obj)
     return qdict_get_int(qobject_to_qdict(obj), "type");
 }
 
-static int token_is_keyword(QObject *obj, const char *value)
-{
-    if (token_get_type(obj) != JSON_KEYWORD) {
-        return 0;
-    }
-
-    return strcmp(token_get_value(obj), value) == 0;
-}
-
 static int token_is_escape(QObject *obj, const char *value)
 {
     if (token_get_type(obj) != JSON_ESCAPE) {
@@ -533,6 +524,7 @@ static QObject *parse_keyword(JSONParserContext *ctxt)
 {
     QObject *token, *ret;
     JSONParserContext saved_ctxt = parser_context_save(ctxt);
+    const char *val;
 
     token = parser_context_pop_token(ctxt);
     if (token == NULL) {
@@ -543,14 +535,16 @@ static QObject *parse_keyword(JSONParserContext *ctxt)
         goto out;
     }
 
-    if (token_is_keyword(token, "true")) {
+    val = token_get_value(token);
+
+    if (!strcmp(val, "true")) {
         ret = QOBJECT(qbool_from_bool(true));
-    } else if (token_is_keyword(token, "false")) {
+    } else if (!strcmp(val, "false")) {
         ret = QOBJECT(qbool_from_bool(false));
-    } else if (token_is_keyword(token, "null")) {
+    } else if (!strcmp(val, "null")) {
         ret = qnull();
     } else {
-        parse_error(ctxt, token, "invalid keyword `%s'", token_get_value(token));
+        parse_error(ctxt, token, "invalid keyword '%s'", val);
         goto out;
     }
 
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 08/13] qjson: Inline token_is_escape() and simplify

[Markus Armbruster]

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Message-Id: <1448486613-17634-8-git-send-email-armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 qobject/json-parser.c | 32 +++++++++++++++-----------------
 1 file changed, 15 insertions(+), 17 deletions(-)

diff --git a/qobject/json-parser.c b/qobject/json-parser.c
index df76cc3..b57cac7 100644
--- a/qobject/json-parser.c
+++ b/qobject/json-parser.c
@@ -63,15 +63,6 @@ static JSONTokenType token_get_type(QObject *obj)
     return qdict_get_int(qobject_to_qdict(obj), "type");
 }
 
-static int token_is_escape(QObject *obj, const char *value)
-{
-    if (token_get_type(obj) != JSON_ESCAPE) {
-        return 0;
-    }
-
-    return (strcmp(token_get_value(obj), value) == 0);
-}
-
 /**
  * Error handler
  */
@@ -560,6 +551,7 @@ static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)
 {
     QObject *token = NULL, *obj;
     JSONParserContext saved_ctxt = parser_context_save(ctxt);
+    const char *val;
 
     if (ap == NULL) {
         goto out;
@@ -570,20 +562,26 @@ static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)
         goto out;
     }
 
-    if (token_is_escape(token, "%p")) {
+    if (token_get_type(token) != JSON_ESCAPE) {
+        goto out;
+    }
+
+    val = token_get_value(token);
+
+    if (!strcmp(val, "%p")) {
         obj = va_arg(*ap, QObject *);
-    } else if (token_is_escape(token, "%i")) {
+    } else if (!strcmp(val, "%i")) {
         obj = QOBJECT(qbool_from_bool(va_arg(*ap, int)));
-    } else if (token_is_escape(token, "%d")) {
+    } else if (!strcmp(val, "%d")) {
         obj = QOBJECT(qint_from_int(va_arg(*ap, int)));
-    } else if (token_is_escape(token, "%ld")) {
+    } else if (!strcmp(val, "%ld")) {
         obj = QOBJECT(qint_from_int(va_arg(*ap, long)));
-    } else if (token_is_escape(token, "%lld") ||
-               token_is_escape(token, "%I64d")) {
+    } else if (!strcmp(val, "%lld") ||
+               !strcmp(val, "%I64d")) {
         obj = QOBJECT(qint_from_int(va_arg(*ap, long long)));
-    } else if (token_is_escape(token, "%s")) {
+    } else if (!strcmp(val, "%s")) {
         obj = QOBJECT(qstring_from_str(va_arg(*ap, const char *)));
-    } else if (token_is_escape(token, "%f")) {
+    } else if (!strcmp(val, "%f")) {
         obj = QOBJECT(qfloat_from_double(va_arg(*ap, double)));
     } else {
         goto out;
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 09/13] qjson: replace QString in JSONLexer with GString

[Markus Armbruster]

From: Paolo Bonzini <pbonzini@redhat.com>

JSONLexer only needs a simple resizable buffer.  json-streamer.c
can allocate memory for each token instead of relying on reference
counting of QStrings.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Message-Id: <1448300659-23559-2-git-send-email-pbonzini@redhat.com>
[Straightforwardly rebased on my patches, checkpatch made happy]
Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 include/qapi/qmp/json-lexer.h    |  8 ++++----
 include/qapi/qmp/json-streamer.h |  1 +
 qobject/json-lexer.c             | 22 ++++++++--------------
 qobject/json-streamer.c          |  9 +++++----
 4 files changed, 18 insertions(+), 22 deletions(-)

diff --git a/include/qapi/qmp/json-lexer.h b/include/qapi/qmp/json-lexer.h
index f3e8dc7..cb456d5 100644
--- a/include/qapi/qmp/json-lexer.h
+++ b/include/qapi/qmp/json-lexer.h
@@ -14,8 +14,7 @@
 #ifndef QEMU_JSON_LEXER_H
 #define QEMU_JSON_LEXER_H
 
-#include "qapi/qmp/qstring.h"
-#include "qapi/qmp/qlist.h"
+#include "glib-compat.h"
 
 typedef enum json_token_type {
     JSON_MIN = 100,
@@ -36,13 +35,14 @@ typedef enum json_token_type {
 
 typedef struct JSONLexer JSONLexer;
 
-typedef void (JSONLexerEmitter)(JSONLexer *, QString *, JSONTokenType, int x, int y);
+typedef void (JSONLexerEmitter)(JSONLexer *, GString *,
+                                JSONTokenType, int x, int y);
 
 struct JSONLexer
 {
     JSONLexerEmitter *emit;
     int state;
-    QString *token;
+    GString *token;
     int x, y;
 };
 
diff --git a/include/qapi/qmp/json-streamer.h b/include/qapi/qmp/json-streamer.h
index 823f7d7..e901144 100644
--- a/include/qapi/qmp/json-streamer.h
+++ b/include/qapi/qmp/json-streamer.h
@@ -14,6 +14,7 @@
 #ifndef QEMU_JSON_STREAMER_H
 #define QEMU_JSON_STREAMER_H
 
+#include <stdint.h>
 #include "qapi/qmp/qlist.h"
 #include "qapi/qmp/json-lexer.h"
 
diff --git a/qobject/json-lexer.c b/qobject/json-lexer.c
index 1df7d5e..92798ae 100644
--- a/qobject/json-lexer.c
+++ b/qobject/json-lexer.c
@@ -11,12 +11,9 @@
  *
  */
 
-#include "qapi/qmp/qstring.h"
-#include "qapi/qmp/qlist.h"
-#include "qapi/qmp/qdict.h"
-#include "qapi/qmp/qint.h"
 #include "qemu-common.h"
 #include "qapi/qmp/json-lexer.h"
+#include <stdint.h>
 
 #define MAX_TOKEN_SIZE (64ULL << 20)
 
@@ -276,7 +273,7 @@ void json_lexer_init(JSONLexer *lexer, JSONLexerEmitter func)
 {
     lexer->emit = func;
     lexer->state = IN_START;
-    lexer->token = qstring_new();
+    lexer->token = g_string_sized_new(3);
     lexer->x = lexer->y = 0;
 }
 
@@ -295,7 +292,7 @@ static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
         new_state = json_lexer[lexer->state][(uint8_t)ch];
         char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state);
         if (char_consumed) {
-            qstring_append_chr(lexer->token, ch);
+            g_string_append_c(lexer->token, ch);
         }
 
         switch (new_state) {
@@ -313,8 +310,7 @@ static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
             lexer->emit(lexer, lexer->token, new_state, lexer->x, lexer->y);
             /* fall through */
         case JSON_SKIP:
-            QDECREF(lexer->token);
-            lexer->token = qstring_new();
+            g_string_truncate(lexer->token, 0);
             new_state = IN_START;
             break;
         case IN_ERROR:
@@ -332,8 +328,7 @@ static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
              * induce an error/flush state.
              */
             lexer->emit(lexer, lexer->token, JSON_ERROR, lexer->x, lexer->y);
-            QDECREF(lexer->token);
-            lexer->token = qstring_new();
+            g_string_truncate(lexer->token, 0);
             new_state = IN_START;
             lexer->state = new_state;
             return 0;
@@ -346,10 +341,9 @@ static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
     /* Do not let a single token grow to an arbitrarily large size,
      * this is a security consideration.
      */
-    if (lexer->token->length > MAX_TOKEN_SIZE) {
+    if (lexer->token->len > MAX_TOKEN_SIZE) {
         lexer->emit(lexer, lexer->token, lexer->state, lexer->x, lexer->y);
-        QDECREF(lexer->token);
-        lexer->token = qstring_new();
+        g_string_truncate(lexer->token, 0);
         lexer->state = IN_START;
     }
 
@@ -379,5 +373,5 @@ int json_lexer_flush(JSONLexer *lexer)
 
 void json_lexer_destroy(JSONLexer *lexer)
 {
-    QDECREF(lexer->token);
+    g_string_free(lexer->token, true);
 }
diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index 4a161a1..7292f3a 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -12,6 +12,7 @@
  */
 
 #include "qapi/qmp/qlist.h"
+#include "qapi/qmp/qstring.h"
 #include "qapi/qmp/qint.h"
 #include "qapi/qmp/qdict.h"
 #include "qemu-common.h"
@@ -21,7 +22,8 @@
 #define MAX_TOKEN_SIZE (64ULL << 20)
 #define MAX_NESTING (1ULL << 10)
 
-static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTokenType type, int x, int y)
+static void json_message_process_token(JSONLexer *lexer, GString *input,
+                                       JSONTokenType type, int x, int y)
 {
     JSONMessageParser *parser = container_of(lexer, JSONMessageParser, lexer);
     QDict *dict;
@@ -45,12 +47,11 @@ static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTok
 
     dict = qdict_new();
     qdict_put(dict, "type", qint_from_int(type));
-    QINCREF(token);
-    qdict_put(dict, "token", token);
+    qdict_put(dict, "token", qstring_from_str(input->str));
     qdict_put(dict, "x", qint_from_int(x));
     qdict_put(dict, "y", qint_from_int(y));
 
-    parser->token_size += token->length;
+    parser->token_size += input->len;
 
     qlist_append(parser->tokens, dict);
 
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 10/13] qjson: Convert to parser to recursive descent

[Markus Armbruster]

We backtrack in parse_value(), even though JSON is LL(1) and thus can
be parsed by straightforward recursive descent.  Do exactly that.

Based on an almost-correct patch from Paolo Bonzini.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
Message-Id: <1448486613-17634-10-git-send-email-armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 qobject/json-parser.c | 165 ++++++++++++++------------------------------------
 1 file changed, 47 insertions(+), 118 deletions(-)

diff --git a/qobject/json-parser.c b/qobject/json-parser.c
index b57cac7..60dd624 100644
--- a/qobject/json-parser.c
+++ b/qobject/json-parser.c
@@ -265,23 +265,6 @@ static QObject *parser_context_peek_token(JSONParserContext *ctxt)
     return token;
 }
 
-static JSONParserContext parser_context_save(JSONParserContext *ctxt)
-{
-    JSONParserContext saved_ctxt = {0};
-    saved_ctxt.tokens.pos = ctxt->tokens.pos;
-    saved_ctxt.tokens.count = ctxt->tokens.count;
-    saved_ctxt.tokens.buf = ctxt->tokens.buf;
-    return saved_ctxt;
-}
-
-static void parser_context_restore(JSONParserContext *ctxt,
-                                   JSONParserContext saved_ctxt)
-{
-    ctxt->tokens.pos = saved_ctxt.tokens.pos;
-    ctxt->tokens.count = saved_ctxt.tokens.count;
-    ctxt->tokens.buf = saved_ctxt.tokens.buf;
-}
-
 static void tokens_append_from_iter(QObject *obj, void *opaque)
 {
     JSONParserContext *ctxt = opaque;
@@ -333,7 +316,6 @@ static void parser_context_free(JSONParserContext *ctxt)
 static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
 {
     QObject *key = NULL, *token = NULL, *value, *peek;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
     peek = parser_context_peek_token(ctxt);
     if (peek == NULL) {
@@ -371,7 +353,6 @@ static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
     return 0;
 
 out:
-    parser_context_restore(ctxt, saved_ctxt);
     qobject_decref(key);
 
     return -1;
@@ -381,16 +362,9 @@ static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
 {
     QDict *dict = NULL;
     QObject *token, *peek;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
     token = parser_context_pop_token(ctxt);
-    if (token == NULL) {
-        goto out;
-    }
-
-    if (token_get_type(token) != JSON_LCURLY) {
-        goto out;
-    }
+    assert(token && token_get_type(token) == JSON_LCURLY);
 
     dict = qdict_new();
 
@@ -434,7 +408,6 @@ static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
     return QOBJECT(dict);
 
 out:
-    parser_context_restore(ctxt, saved_ctxt);
     QDECREF(dict);
     return NULL;
 }
@@ -443,16 +416,9 @@ static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
 {
     QList *list = NULL;
     QObject *token, *peek;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
     token = parser_context_pop_token(ctxt);
-    if (token == NULL) {
-        goto out;
-    }
-
-    if (token_get_type(token) != JSON_LSQUARE) {
-        goto out;
-    }
+    assert(token && token_get_type(token) == JSON_LSQUARE);
 
     list = qlist_new();
 
@@ -506,109 +472,72 @@ static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
     return QOBJECT(list);
 
 out:
-    parser_context_restore(ctxt, saved_ctxt);
     QDECREF(list);
     return NULL;
 }
 
 static QObject *parse_keyword(JSONParserContext *ctxt)
 {
-    QObject *token, *ret;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
+    QObject *token;
     const char *val;
 
     token = parser_context_pop_token(ctxt);
-    if (token == NULL) {
-        goto out;
-    }
-
-    if (token_get_type(token) != JSON_KEYWORD) {
-        goto out;
-    }
-
+    assert(token && token_get_type(token) == JSON_KEYWORD);
     val = token_get_value(token);
 
     if (!strcmp(val, "true")) {
-        ret = QOBJECT(qbool_from_bool(true));
+        return QOBJECT(qbool_from_bool(true));
     } else if (!strcmp(val, "false")) {
-        ret = QOBJECT(qbool_from_bool(false));
+        return QOBJECT(qbool_from_bool(false));
     } else if (!strcmp(val, "null")) {
-        ret = qnull();
-    } else {
-        parse_error(ctxt, token, "invalid keyword '%s'", val);
-        goto out;
+        return qnull();
     }
-
-    return ret;
-
-out: 
-    parser_context_restore(ctxt, saved_ctxt);
-
+    parse_error(ctxt, token, "invalid keyword '%s'", val);
     return NULL;
 }
 
 static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)
 {
-    QObject *token = NULL, *obj;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
+    QObject *token;
     const char *val;
 
     if (ap == NULL) {
-        goto out;
+        return NULL;
     }
 
     token = parser_context_pop_token(ctxt);
-    if (token == NULL) {
-        goto out;
-    }
-
-    if (token_get_type(token) != JSON_ESCAPE) {
-        goto out;
-    }
-
+    assert(token && token_get_type(token) == JSON_ESCAPE);
     val = token_get_value(token);
 
     if (!strcmp(val, "%p")) {
-        obj = va_arg(*ap, QObject *);
+        return va_arg(*ap, QObject *);
     } else if (!strcmp(val, "%i")) {
-        obj = QOBJECT(qbool_from_bool(va_arg(*ap, int)));
+        return QOBJECT(qbool_from_bool(va_arg(*ap, int)));
     } else if (!strcmp(val, "%d")) {
-        obj = QOBJECT(qint_from_int(va_arg(*ap, int)));
+        return QOBJECT(qint_from_int(va_arg(*ap, int)));
     } else if (!strcmp(val, "%ld")) {
-        obj = QOBJECT(qint_from_int(va_arg(*ap, long)));
+        return QOBJECT(qint_from_int(va_arg(*ap, long)));
     } else if (!strcmp(val, "%lld") ||
                !strcmp(val, "%I64d")) {
-        obj = QOBJECT(qint_from_int(va_arg(*ap, long long)));
+        return QOBJECT(qint_from_int(va_arg(*ap, long long)));
     } else if (!strcmp(val, "%s")) {
-        obj = QOBJECT(qstring_from_str(va_arg(*ap, const char *)));
+        return QOBJECT(qstring_from_str(va_arg(*ap, const char *)));
     } else if (!strcmp(val, "%f")) {
-        obj = QOBJECT(qfloat_from_double(va_arg(*ap, double)));
-    } else {
-        goto out;
+        return QOBJECT(qfloat_from_double(va_arg(*ap, double)));
     }
-
-    return obj;
-
-out:
-    parser_context_restore(ctxt, saved_ctxt);
-
     return NULL;
 }
 
 static QObject *parse_literal(JSONParserContext *ctxt)
 {
-    QObject *token, *obj;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
+    QObject *token;
 
     token = parser_context_pop_token(ctxt);
-    if (token == NULL) {
-        goto out;
-    }
+    assert(token);
 
     switch (token_get_type(token)) {
     case JSON_STRING:
-        obj = QOBJECT(qstring_from_escaped_str(ctxt, token));
-        break;
+        return QOBJECT(qstring_from_escaped_str(ctxt, token));
     case JSON_INTEGER: {
         /* A possibility exists that this is a whole-valued float where the
          * fractional part was left out due to being 0 (.0). It's not a big
@@ -627,46 +556,46 @@ static QObject *parse_literal(JSONParserContext *ctxt)
         errno = 0; /* strtoll doesn't set errno on success */
         value = strtoll(token_get_value(token), NULL, 10);
         if (errno != ERANGE) {
-            obj = QOBJECT(qint_from_int(value));
-            break;
+            return QOBJECT(qint_from_int(value));
         }
         /* fall through to JSON_FLOAT */
     }
     case JSON_FLOAT:
         /* FIXME dependent on locale */
-        obj = QOBJECT(qfloat_from_double(strtod(token_get_value(token), NULL)));
-        break;
+        return QOBJECT(qfloat_from_double(strtod(token_get_value(token),
+                                                 NULL)));
     default:
-        goto out;
+        abort();
     }
-
-    return obj;
-
-out:
-    parser_context_restore(ctxt, saved_ctxt);
-
-    return NULL;
 }
 
 static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
 {
-    QObject *obj;
+    QObject *token;
 
-    obj = parse_object(ctxt, ap);
-    if (obj == NULL) {
-        obj = parse_array(ctxt, ap);
-    }
-    if (obj == NULL) {
-        obj = parse_escape(ctxt, ap);
-    }
-    if (obj == NULL) {
-        obj = parse_keyword(ctxt);
-    } 
-    if (obj == NULL) {
-        obj = parse_literal(ctxt);
+    token = parser_context_peek_token(ctxt);
+    if (token == NULL) {
+        parse_error(ctxt, NULL, "premature EOI");
+        return NULL;
     }
 
-    return obj;
+    switch (token_get_type(token)) {
+    case JSON_LCURLY:
+        return parse_object(ctxt, ap);
+    case JSON_LSQUARE:
+        return parse_array(ctxt, ap);
+    case JSON_ESCAPE:
+        return parse_escape(ctxt, ap);
+    case JSON_INTEGER:
+    case JSON_FLOAT:
+    case JSON_STRING:
+        return parse_literal(ctxt);
+    case JSON_KEYWORD:
+        return parse_keyword(ctxt);
+    default:
+        parse_error(ctxt, token, "expecting value");
+        return NULL;
+    }
 }
 
 QObject *json_parser_parse(QList *tokens, va_list *ap)
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 11/13] qjson: store tokens in a GQueue

[Markus Armbruster]

From: Paolo Bonzini <pbonzini@redhat.com>

Even though we still have the "streamer" concept, the tokens can now
be deleted as they are read.  While doing so convert from QList to
GQueue, since the next step will make tokens not a QObject and we
will have to do the conversion anyway.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Message-Id: <1448300659-23559-4-git-send-email-pbonzini@redhat.com>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 include/qapi/qmp/json-parser.h   |  4 +--
 include/qapi/qmp/json-streamer.h |  8 ++---
 monitor.c                        |  2 +-
 qga/main.c                       |  2 +-
 qobject/json-parser.c            | 65 +++++++++++++---------------------------
 qobject/json-streamer.c          | 25 +++++++++-------
 qobject/qjson.c                  |  2 +-
 tests/libqtest.c                 |  2 +-
 8 files changed, 45 insertions(+), 65 deletions(-)

diff --git a/include/qapi/qmp/json-parser.h b/include/qapi/qmp/json-parser.h
index 44d88f3..fea89f8 100644
--- a/include/qapi/qmp/json-parser.h
+++ b/include/qapi/qmp/json-parser.h
@@ -18,7 +18,7 @@
 #include "qapi/qmp/qlist.h"
 #include "qapi/error.h"
 
-QObject *json_parser_parse(QList *tokens, va_list *ap);
-QObject *json_parser_parse_err(QList *tokens, va_list *ap, Error **errp);
+QObject *json_parser_parse(GQueue *tokens, va_list *ap);
+QObject *json_parser_parse_err(GQueue *tokens, va_list *ap, Error **errp);
 
 #endif
diff --git a/include/qapi/qmp/json-streamer.h b/include/qapi/qmp/json-streamer.h
index e901144..e9f2937 100644
--- a/include/qapi/qmp/json-streamer.h
+++ b/include/qapi/qmp/json-streamer.h
@@ -15,21 +15,21 @@
 #define QEMU_JSON_STREAMER_H
 
 #include <stdint.h>
-#include "qapi/qmp/qlist.h"
+#include "glib-compat.h"
 #include "qapi/qmp/json-lexer.h"
 
 typedef struct JSONMessageParser
 {
-    void (*emit)(struct JSONMessageParser *parser, QList *tokens);
+    void (*emit)(struct JSONMessageParser *parser, GQueue *tokens);
     JSONLexer lexer;
     int brace_count;
     int bracket_count;
-    QList *tokens;
+    GQueue *tokens;
     uint64_t token_size;
 } JSONMessageParser;
 
 void json_message_parser_init(JSONMessageParser *parser,
-                              void (*func)(JSONMessageParser *, QList *));
+                              void (*func)(JSONMessageParser *, GQueue *));
 
 int json_message_parser_feed(JSONMessageParser *parser,
                              const char *buffer, size_t size);
diff --git a/monitor.c b/monitor.c
index 49073ac..9a35d72 100644
--- a/monitor.c
+++ b/monitor.c
@@ -3849,7 +3849,7 @@ static QDict *qmp_check_input_obj(QObject *input_obj, Error **errp)
     return input_dict;
 }
 
-static void handle_qmp_command(JSONMessageParser *parser, QList *tokens)
+static void handle_qmp_command(JSONMessageParser *parser, GQueue *tokens)
 {
     Error *local_err = NULL;
     QObject *obj, *data;
diff --git a/qga/main.c b/qga/main.c
index d2a0ffc..f83a97d 100644
--- a/qga/main.c
+++ b/qga/main.c
@@ -570,7 +570,7 @@ static void process_command(GAState *s, QDict *req)
 }
 
 /* handle requests/control events coming in over the channel */
-static void process_event(JSONMessageParser *parser, QList *tokens)
+static void process_event(JSONMessageParser *parser, GQueue *tokens)
 {
     GAState *s = container_of(parser, GAState, parser);
     QDict *qdict;
diff --git a/qobject/json-parser.c b/qobject/json-parser.c
index 60dd624..5a84951 100644
--- a/qobject/json-parser.c
+++ b/qobject/json-parser.c
@@ -26,11 +26,8 @@
 typedef struct JSONParserContext
 {
     Error *err;
-    struct {
-        QObject **buf;
-        size_t pos;
-        size_t count;
-    } tokens;
+    QObject *current;
+    GQueue *buf;
 } JSONParserContext;
 
 #define BUG_ON(cond) assert(!(cond))
@@ -243,56 +240,34 @@ out:
     return NULL;
 }
 
+/* Note: unless the token object returned by parser_context_peek_token
+ * or parser_context_pop_token is explicitly incref'd, it will be
+ * deleted as soon as parser_context_pop_token is called again.
+ */
 static QObject *parser_context_pop_token(JSONParserContext *ctxt)
 {
-    QObject *token;
-    g_assert(ctxt->tokens.pos < ctxt->tokens.count);
-    token = ctxt->tokens.buf[ctxt->tokens.pos];
-    ctxt->tokens.pos++;
-    return token;
+    qobject_decref(ctxt->current);
+    assert(!g_queue_is_empty(ctxt->buf));
+    ctxt->current = g_queue_pop_head(ctxt->buf);
+    return ctxt->current;
 }
 
-/* Note: parser_context_{peek|pop}_token do not increment the
- * token object's refcount. In both cases the references will continue
- * to be tracked and cleaned up in parser_context_free(), so do not
- * attempt to free the token object.
- */
 static QObject *parser_context_peek_token(JSONParserContext *ctxt)
 {
-    QObject *token;
-    g_assert(ctxt->tokens.pos < ctxt->tokens.count);
-    token = ctxt->tokens.buf[ctxt->tokens.pos];
-    return token;
+    assert(!g_queue_is_empty(ctxt->buf));
+    return g_queue_peek_head(ctxt->buf);
 }
 
-static void tokens_append_from_iter(QObject *obj, void *opaque)
-{
-    JSONParserContext *ctxt = opaque;
-    g_assert(ctxt->tokens.pos < ctxt->tokens.count);
-    ctxt->tokens.buf[ctxt->tokens.pos++] = obj;
-    qobject_incref(obj);
-}
-
-static JSONParserContext *parser_context_new(QList *tokens)
+static JSONParserContext *parser_context_new(GQueue *tokens)
 {
     JSONParserContext *ctxt;
-    size_t count;
 
     if (!tokens) {
         return NULL;
     }
 
-    count = qlist_size(tokens);
-    if (count == 0) {
-        return NULL;
-    }
-
     ctxt = g_malloc0(sizeof(JSONParserContext));
-    ctxt->tokens.pos = 0;
-    ctxt->tokens.count = count;
-    ctxt->tokens.buf = g_malloc(count * sizeof(QObject *));
-    qlist_iter(tokens, tokens_append_from_iter, ctxt);
-    ctxt->tokens.pos = 0;
+    ctxt->buf = tokens;
 
     return ctxt;
 }
@@ -300,12 +275,12 @@ static JSONParserContext *parser_context_new(QList *tokens)
 /* to support error propagation, ctxt->err must be freed separately */
 static void parser_context_free(JSONParserContext *ctxt)
 {
-    int i;
     if (ctxt) {
-        for (i = 0; i < ctxt->tokens.count; i++) {
-            qobject_decref(ctxt->tokens.buf[i]);
+        while (!g_queue_is_empty(ctxt->buf)) {
+            parser_context_pop_token(ctxt);
         }
-        g_free(ctxt->tokens.buf);
+        qobject_decref(ctxt->current);
+        g_queue_free(ctxt->buf);
         g_free(ctxt);
     }
 }
@@ -598,12 +573,12 @@ static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
     }
 }
 
-QObject *json_parser_parse(QList *tokens, va_list *ap)
+QObject *json_parser_parse(GQueue *tokens, va_list *ap)
 {
     return json_parser_parse_err(tokens, ap, NULL);
 }
 
-QObject *json_parser_parse_err(QList *tokens, va_list *ap, Error **errp)
+QObject *json_parser_parse_err(GQueue *tokens, va_list *ap, Error **errp)
 {
     JSONParserContext *ctxt = parser_context_new(tokens);
     QObject *result;
diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index 7292f3a..f7a3e78 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -22,6 +22,14 @@
 #define MAX_TOKEN_SIZE (64ULL << 20)
 #define MAX_NESTING (1ULL << 10)
 
+static void json_message_free_tokens(JSONMessageParser *parser)
+{
+    if (parser->tokens) {
+        g_queue_free(parser->tokens);
+        parser->tokens = NULL;
+    }
+}
+
 static void json_message_process_token(JSONLexer *lexer, GString *input,
                                        JSONTokenType type, int x, int y)
 {
@@ -53,7 +61,7 @@ static void json_message_process_token(JSONLexer *lexer, GString *input,
 
     parser->token_size += input->len;
 
-    qlist_append(parser->tokens, dict);
+    g_queue_push_tail(parser->tokens, dict);
 
     if (type == JSON_ERROR) {
         goto out_emit_bad;
@@ -77,27 +85,24 @@ out_emit_bad:
      * Clear out token list and tell the parser to emit an error
      * indication by passing it a NULL list
      */
-    QDECREF(parser->tokens);
-    parser->tokens = NULL;
+    json_message_free_tokens(parser);
 out_emit:
     /* send current list of tokens to parser and reset tokenizer */
     parser->brace_count = 0;
     parser->bracket_count = 0;
+    /* parser->emit takes ownership of parser->tokens.  */
     parser->emit(parser, parser->tokens);
-    if (parser->tokens) {
-        QDECREF(parser->tokens);
-    }
-    parser->tokens = qlist_new();
+    parser->tokens = g_queue_new();
     parser->token_size = 0;
 }
 
 void json_message_parser_init(JSONMessageParser *parser,
-                              void (*func)(JSONMessageParser *, QList *))
+                              void (*func)(JSONMessageParser *, GQueue *))
 {
     parser->emit = func;
     parser->brace_count = 0;
     parser->bracket_count = 0;
-    parser->tokens = qlist_new();
+    parser->tokens = g_queue_new();
     parser->token_size = 0;
 
     json_lexer_init(&parser->lexer, json_message_process_token);
@@ -117,5 +122,5 @@ int json_message_parser_flush(JSONMessageParser *parser)
 void json_message_parser_destroy(JSONMessageParser *parser)
 {
     json_lexer_destroy(&parser->lexer);
-    QDECREF(parser->tokens);
+    json_message_free_tokens(parser);
 }
diff --git a/qobject/qjson.c b/qobject/qjson.c
index 33f8ef5..a3e6a7c 100644
--- a/qobject/qjson.c
+++ b/qobject/qjson.c
@@ -28,7 +28,7 @@ typedef struct JSONParsingState
     QObject *result;
 } JSONParsingState;
 
-static void parse_json(JSONMessageParser *parser, QList *tokens)
+static void parse_json(JSONMessageParser *parser, GQueue *tokens)
 {
     JSONParsingState *s = container_of(parser, JSONParsingState, parser);
     s->result = json_parser_parse(tokens, s->ap);
diff --git a/tests/libqtest.c b/tests/libqtest.c
index f6f3d7a..9753161 100644
--- a/tests/libqtest.c
+++ b/tests/libqtest.c
@@ -351,7 +351,7 @@ typedef struct {
     QDict *response;
 } QMPResponseParser;
 
-static void qmp_response(JSONMessageParser *parser, QList *tokens)
+static void qmp_response(JSONMessageParser *parser, GQueue *tokens)
 {
     QMPResponseParser *qmp = container_of(parser, QMPResponseParser, parser);
     QObject *obj;
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 12/13] qjson: surprise, allocating 6 QObjects per token is expensive

[Markus Armbruster]

From: Paolo Bonzini <pbonzini@redhat.com>

Replace the contents of the tokens GQueue with a simple struct.  This cuts
the amount of memory allocated by tests/check-qjson from ~500MB to ~20MB,
and the execution time from 600ms to 80ms on my laptop.  Still a lot (some
could be saved by using an intrusive list, such as QSIMPLEQ, instead of
the GQueue), but the savings are already massive and the right thing to
do would probably be to get rid of json-streamer completely.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
Message-Id: <1448300659-23559-5-git-send-email-pbonzini@redhat.com>
[Straightforwardly rebased on my patches]
Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 include/qapi/qmp/json-streamer.h |   7 +++
 qobject/json-parser.c            | 115 ++++++++++++++++-----------------------
 qobject/json-streamer.c          |  19 +++----
 3 files changed, 63 insertions(+), 78 deletions(-)

diff --git a/include/qapi/qmp/json-streamer.h b/include/qapi/qmp/json-streamer.h
index e9f2937..09b3d3e 100644
--- a/include/qapi/qmp/json-streamer.h
+++ b/include/qapi/qmp/json-streamer.h
@@ -18,6 +18,13 @@
 #include "glib-compat.h"
 #include "qapi/qmp/json-lexer.h"
 
+typedef struct JSONToken {
+    int type;
+    int x;
+    int y;
+    char str[];
+} JSONToken;
+
 typedef struct JSONMessageParser
 {
     void (*emit)(struct JSONMessageParser *parser, GQueue *tokens);
diff --git a/qobject/json-parser.c b/qobject/json-parser.c
index 5a84951..3c5d35d 100644
--- a/qobject/json-parser.c
+++ b/qobject/json-parser.c
@@ -22,11 +22,12 @@
 #include "qapi/qmp/qbool.h"
 #include "qapi/qmp/json-parser.h"
 #include "qapi/qmp/json-lexer.h"
+#include "qapi/qmp/json-streamer.h"
 
 typedef struct JSONParserContext
 {
     Error *err;
-    QObject *current;
+    JSONToken *current;
     GQueue *buf;
 } JSONParserContext;
 
@@ -44,27 +45,10 @@ typedef struct JSONParserContext
 static QObject *parse_value(JSONParserContext *ctxt, va_list *ap);
 
 /**
- * Token manipulators
- *
- * tokens are dictionaries that contain a type, a string value, and geometry information
- * about a token identified by the lexer.  These are routines that make working with
- * these objects a bit easier.
- */
-static const char *token_get_value(QObject *obj)
-{
-    return qdict_get_str(qobject_to_qdict(obj), "token");
-}
-
-static JSONTokenType token_get_type(QObject *obj)
-{
-    return qdict_get_int(qobject_to_qdict(obj), "type");
-}
-
-/**
  * Error handler
  */
 static void GCC_FMT_ATTR(3, 4) parse_error(JSONParserContext *ctxt,
-                                           QObject *token, const char *msg, ...)
+                                           JSONToken *token, const char *msg, ...)
 {
     va_list ap;
     char message[1024];
@@ -142,9 +126,10 @@ static int hex2decimal(char ch)
  *      \t
  *      \u four-hex-digits 
  */
-static QString *qstring_from_escaped_str(JSONParserContext *ctxt, QObject *token)
+static QString *qstring_from_escaped_str(JSONParserContext *ctxt,
+                                         JSONToken *token)
 {
-    const char *ptr = token_get_value(token);
+    const char *ptr = token->str;
     QString *str;
     int double_quote = 1;
 
@@ -240,19 +225,19 @@ out:
     return NULL;
 }
 
-/* Note: unless the token object returned by parser_context_peek_token
- * or parser_context_pop_token is explicitly incref'd, it will be
- * deleted as soon as parser_context_pop_token is called again.
+/* Note: the token object returned by parser_context_peek_token or
+ * parser_context_pop_token is deleted as soon as parser_context_pop_token
+ * is called again.
  */
-static QObject *parser_context_pop_token(JSONParserContext *ctxt)
+static JSONToken *parser_context_pop_token(JSONParserContext *ctxt)
 {
-    qobject_decref(ctxt->current);
+    g_free(ctxt->current);
     assert(!g_queue_is_empty(ctxt->buf));
     ctxt->current = g_queue_pop_head(ctxt->buf);
     return ctxt->current;
 }
 
-static QObject *parser_context_peek_token(JSONParserContext *ctxt)
+static JSONToken *parser_context_peek_token(JSONParserContext *ctxt)
 {
     assert(!g_queue_is_empty(ctxt->buf));
     return g_queue_peek_head(ctxt->buf);
@@ -279,7 +264,7 @@ static void parser_context_free(JSONParserContext *ctxt)
         while (!g_queue_is_empty(ctxt->buf)) {
             parser_context_pop_token(ctxt);
         }
-        qobject_decref(ctxt->current);
+        g_free(ctxt->current);
         g_queue_free(ctxt->buf);
         g_free(ctxt);
     }
@@ -290,7 +275,8 @@ static void parser_context_free(JSONParserContext *ctxt)
  */
 static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
 {
-    QObject *key = NULL, *token = NULL, *value, *peek;
+    QObject *key = NULL, *value;
+    JSONToken *peek, *token;
 
     peek = parser_context_peek_token(ctxt);
     if (peek == NULL) {
@@ -310,7 +296,7 @@ static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
         goto out;
     }
 
-    if (token_get_type(token) != JSON_COLON) {
+    if (token->type != JSON_COLON) {
         parse_error(ctxt, token, "missing : in object pair");
         goto out;
     }
@@ -336,10 +322,10 @@ out:
 static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
 {
     QDict *dict = NULL;
-    QObject *token, *peek;
+    JSONToken *token, *peek;
 
     token = parser_context_pop_token(ctxt);
-    assert(token && token_get_type(token) == JSON_LCURLY);
+    assert(token && token->type == JSON_LCURLY);
 
     dict = qdict_new();
 
@@ -349,7 +335,7 @@ static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
         goto out;
     }
 
-    if (token_get_type(peek) != JSON_RCURLY) {
+    if (peek->type != JSON_RCURLY) {
         if (parse_pair(ctxt, dict, ap) == -1) {
             goto out;
         }
@@ -360,8 +346,8 @@ static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
             goto out;
         }
 
-        while (token_get_type(token) != JSON_RCURLY) {
-            if (token_get_type(token) != JSON_COMMA) {
+        while (token->type != JSON_RCURLY) {
+            if (token->type != JSON_COMMA) {
                 parse_error(ctxt, token, "expected separator in dict");
                 goto out;
             }
@@ -390,10 +376,10 @@ out:
 static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
 {
     QList *list = NULL;
-    QObject *token, *peek;
+    JSONToken *token, *peek;
 
     token = parser_context_pop_token(ctxt);
-    assert(token && token_get_type(token) == JSON_LSQUARE);
+    assert(token && token->type == JSON_LSQUARE);
 
     list = qlist_new();
 
@@ -403,7 +389,7 @@ static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
         goto out;
     }
 
-    if (token_get_type(peek) != JSON_RSQUARE) {
+    if (peek->type != JSON_RSQUARE) {
         QObject *obj;
 
         obj = parse_value(ctxt, ap);
@@ -420,8 +406,8 @@ static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
             goto out;
         }
 
-        while (token_get_type(token) != JSON_RSQUARE) {
-            if (token_get_type(token) != JSON_COMMA) {
+        while (token->type != JSON_RSQUARE) {
+            if (token->type != JSON_COMMA) {
                 parse_error(ctxt, token, "expected separator in list");
                 goto out;
             }
@@ -453,51 +439,47 @@ out:
 
 static QObject *parse_keyword(JSONParserContext *ctxt)
 {
-    QObject *token;
-    const char *val;
+    JSONToken *token;
 
     token = parser_context_pop_token(ctxt);
-    assert(token && token_get_type(token) == JSON_KEYWORD);
-    val = token_get_value(token);
+    assert(token && token->type == JSON_KEYWORD);
 
-    if (!strcmp(val, "true")) {
+    if (!strcmp(token->str, "true")) {
         return QOBJECT(qbool_from_bool(true));
-    } else if (!strcmp(val, "false")) {
+    } else if (!strcmp(token->str, "false")) {
         return QOBJECT(qbool_from_bool(false));
-    } else if (!strcmp(val, "null")) {
+    } else if (!strcmp(token->str, "null")) {
         return qnull();
     }
-    parse_error(ctxt, token, "invalid keyword '%s'", val);
+    parse_error(ctxt, token, "invalid keyword '%s'", token->str);
     return NULL;
 }
 
 static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)
 {
-    QObject *token;
-    const char *val;
+    JSONToken *token;
 
     if (ap == NULL) {
         return NULL;
     }
 
     token = parser_context_pop_token(ctxt);
-    assert(token && token_get_type(token) == JSON_ESCAPE);
-    val = token_get_value(token);
+    assert(token && token->type == JSON_ESCAPE);
 
-    if (!strcmp(val, "%p")) {
+    if (!strcmp(token->str, "%p")) {
         return va_arg(*ap, QObject *);
-    } else if (!strcmp(val, "%i")) {
+    } else if (!strcmp(token->str, "%i")) {
         return QOBJECT(qbool_from_bool(va_arg(*ap, int)));
-    } else if (!strcmp(val, "%d")) {
+    } else if (!strcmp(token->str, "%d")) {
         return QOBJECT(qint_from_int(va_arg(*ap, int)));
-    } else if (!strcmp(val, "%ld")) {
+    } else if (!strcmp(token->str, "%ld")) {
         return QOBJECT(qint_from_int(va_arg(*ap, long)));
-    } else if (!strcmp(val, "%lld") ||
-               !strcmp(val, "%I64d")) {
+    } else if (!strcmp(token->str, "%lld") ||
+               !strcmp(token->str, "%I64d")) {
         return QOBJECT(qint_from_int(va_arg(*ap, long long)));
-    } else if (!strcmp(val, "%s")) {
+    } else if (!strcmp(token->str, "%s")) {
         return QOBJECT(qstring_from_str(va_arg(*ap, const char *)));
-    } else if (!strcmp(val, "%f")) {
+    } else if (!strcmp(token->str, "%f")) {
         return QOBJECT(qfloat_from_double(va_arg(*ap, double)));
     }
     return NULL;
@@ -505,12 +487,12 @@ static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)
 
 static QObject *parse_literal(JSONParserContext *ctxt)
 {
-    QObject *token;
+    JSONToken *token;
 
     token = parser_context_pop_token(ctxt);
     assert(token);
 
-    switch (token_get_type(token)) {
+    switch (token->type) {
     case JSON_STRING:
         return QOBJECT(qstring_from_escaped_str(ctxt, token));
     case JSON_INTEGER: {
@@ -529,7 +511,7 @@ static QObject *parse_literal(JSONParserContext *ctxt)
         int64_t value;
 
         errno = 0; /* strtoll doesn't set errno on success */
-        value = strtoll(token_get_value(token), NULL, 10);
+        value = strtoll(token->str, NULL, 10);
         if (errno != ERANGE) {
             return QOBJECT(qint_from_int(value));
         }
@@ -537,8 +519,7 @@ static QObject *parse_literal(JSONParserContext *ctxt)
     }
     case JSON_FLOAT:
         /* FIXME dependent on locale */
-        return QOBJECT(qfloat_from_double(strtod(token_get_value(token),
-                                                 NULL)));
+        return QOBJECT(qfloat_from_double(strtod(token->str, NULL)));
     default:
         abort();
     }
@@ -546,7 +527,7 @@ static QObject *parse_literal(JSONParserContext *ctxt)
 
 static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
 {
-    QObject *token;
+    JSONToken *token;
 
     token = parser_context_peek_token(ctxt);
     if (token == NULL) {
@@ -554,7 +535,7 @@ static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
         return NULL;
     }
 
-    switch (token_get_type(token)) {
+    switch (token->type) {
     case JSON_LCURLY:
         return parse_object(ctxt, ap);
     case JSON_LSQUARE:
diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index f7a3e78..e87230d 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -11,10 +11,6 @@
  *
  */
 
-#include "qapi/qmp/qlist.h"
-#include "qapi/qmp/qstring.h"
-#include "qapi/qmp/qint.h"
-#include "qapi/qmp/qdict.h"
 #include "qemu-common.h"
 #include "qapi/qmp/json-lexer.h"
 #include "qapi/qmp/json-streamer.h"
@@ -34,7 +30,7 @@ static void json_message_process_token(JSONLexer *lexer, GString *input,
                                        JSONTokenType type, int x, int y)
 {
     JSONMessageParser *parser = container_of(lexer, JSONMessageParser, lexer);
-    QDict *dict;
+    JSONToken *token;
 
     switch (type) {
     case JSON_LCURLY:
@@ -53,15 +49,16 @@ static void json_message_process_token(JSONLexer *lexer, GString *input,
         break;
     }
 
-    dict = qdict_new();
-    qdict_put(dict, "type", qint_from_int(type));
-    qdict_put(dict, "token", qstring_from_str(input->str));
-    qdict_put(dict, "x", qint_from_int(x));
-    qdict_put(dict, "y", qint_from_int(y));
+    token = g_malloc(sizeof(JSONToken) + input->len + 1);
+    token->type = type;
+    memcpy(token->str, input->str, input->len);
+    token->str[input->len] = 0;
+    token->x = x;
+    token->y = y;
 
     parser->token_size += input->len;
 
-    g_queue_push_tail(parser->tokens, dict);
+    g_queue_push_tail(parser->tokens, token);
 
     if (type == JSON_ERROR) {
         goto out_emit_bad;
-- 
2.4.3

[Qemu-devel] [PULL for-2.5 13/13] qjson: Limit number of tokens in addition to total size

[Markus Armbruster]

Commit 29c75dd "json-streamer: limit the maximum recursion depth and
maximum token count" attempts to guard against excessive heap usage by
limiting total token size (it says "token count", but that's a lie).

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: 37 bytes on my
system.

Tighten this up: limit the token count to 2Mi.  Chosen to roughly
match the 64MiB total token size limit.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
Message-Id: <1448486613-17634-13-git-send-email-armbru@redhat.com>
---
 qobject/json-streamer.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index e87230d..a4db4b8 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -16,6 +16,7 @@
 #include "qapi/qmp/json-streamer.h"
 
 #define MAX_TOKEN_SIZE (64ULL << 20)
+#define MAX_TOKEN_COUNT (2ULL << 20)
 #define MAX_NESTING (1ULL << 10)
 
 static void json_message_free_tokens(JSONMessageParser *parser)
@@ -68,6 +69,7 @@ static void json_message_process_token(JSONLexer *lexer, GString *input,
          parser->bracket_count == 0)) {
         goto out_emit;
     } else if (parser->token_size > MAX_TOKEN_SIZE ||
+               g_queue_get_length(parser->tokens) > MAX_TOKEN_COUNT ||
                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.
-- 
2.4.3

Re: [Qemu-devel] [PULL for-2.5 00/13] QMP and QObject patches

[Peter Maydell]

On 26 November 2015 at 12:47, Markus Armbruster <armbru@redhat.com> wrote:
> The following changes since commit 1a4dab849d5d06191ab5e5850f6b8bfcad8ceb47:
>
>   Merge remote-tracking branch 'remotes/kevin/tags/for-upstream' into staging (2015-11-25 14:47:06 +0000)
>
> are available in the git repository at:
>
>   git://repo.or.cz/qemu/armbru.git tags/pull-monitor-2015-11-26
>
> for you to fetch changes up to df649835fe48f635a93316fdefe96ced7189316e:
>
>   qjson: Limit number of tokens in addition to total size (2015-11-26 10:07:07 +0100)
>
> ----------------------------------------------------------------
> QMP and QObject patches
>
> ----------------------------------------------------------------
> Markus Armbruster (10):
>       monitor: Plug memory leak on QMP error
>       qjson: Apply nesting limit more sanely
>       qjson: Don't crash when input exceeds nesting limit
>       check-qjson: Add test for JSON nesting depth limit
>       qjson: Spell out some silent assumptions
>       qjson: Give each of the six structural chars its own token type
>       qjson: Inline token_is_keyword() and simplify
>       qjson: Inline token_is_escape() and simplify
>       qjson: Convert to parser to recursive descent
>       qjson: Limit number of tokens in addition to total size
>
> Paolo Bonzini (3):
>       qjson: replace QString in JSONLexer with GString
>       qjson: store tokens in a GQueue
>       qjson: surprise, allocating 6 QObjects per token is expensive


Applied, thanks.

-- PMM