[Qemu-devel] [PATCH v3 for-2.5 00/12] qjson: Fix crash & save a lot of memory

[Qemu-devel] [PATCH v3 for-2.5 00/12] qjson: Fix crash & save a lot of memory

[Markus Armbruster]

This is a fusion of my "[PATCH v2 0/4] json-streamer: Fix up code to
limit nesting and size" and Paolo's "[PATCH v2 for-2.5? 0/4] qjson:
save a lot of memory", with four straightforward cleanups thrown in to
simplify the later patches.

PATCH 01-03 are about the nesting limit.

PATCH 04-07 are cleanups.

PATCH 09-11 are Paolo's, except I pretty much rewrote PATCH 10 to
fully kill the backtracking.

PATCH 12 limits the number of tokens in addition to the total token
size.

Why 2.5?  In my opinion:

* PATCH 01-03 are simple fixes plus a new test.

* PATCH 04-11 reduce memory usage dramatically.  Makes check-qjson's
  large_dict test (~100k tokens) run more than ten times faster.

  If this is deemed too risky for 2.5, PATCH 12 needs to be replaced
  by v2 (different commit message, *much* lower limit).

* PATCH 12 is simple enough.

Markus Armbruster (9):
  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                        |   2 +-
 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, 223 insertions(+), 313 deletions(-)

-- 
2.4.3

[Qemu-devel] [PATCH v3 for-2.5 01/12] 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>
---
 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] [PATCH v3 for-2.5 02/12] 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>
---
 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] [PATCH v3 for-2.5 03/12] 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>
---
 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] [PATCH v3 for-2.5 04/12] qjson: Spell out some silent assumptions

[Markus Armbruster]

Signed-off-by: Markus Armbruster <armbru@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] [PATCH v3 for-2.5 05/12] 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>
---
 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] [PATCH v3 for-2.5 06/12] qjson: Inline token_is_keyword() and simplify

[Markus Armbruster]

Signed-off-by: Markus Armbruster <armbru@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] [PATCH v3 for-2.5 07/12] qjson: Inline token_is_escape() and simplify

[Markus Armbruster]

Signed-off-by: Markus Armbruster <armbru@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] [PATCH v3 for-2.5 08/12] 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>
---
 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] [PATCH v3 for-2.5 09/12] 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: Markus Armbruster <armbru@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] [PATCH v3 for-2.5 10/12] 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>
---
 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] [PATCH v3 for-2.5 11/12] 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>
---
 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] [PATCH v3 for-2.5 12/12] 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>
---
 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] [PATCH v3 for-2.5 04/12] qjson: Spell out some silent assumptions

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 663 bytes --]

On 11/25/2015 02:23 PM, Markus Armbruster wrote:
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---
>  include/qapi/qmp/json-lexer.h | 3 ++-
>  qobject/json-lexer.c          | 7 ++++++-
>  2 files changed, 8 insertions(+), 2 deletions(-)

>  
> +QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START);

I see why the casts are needed here (otherwise, you are comparing two
different enum types, which can trigger warnings).  Perhaps one cast is
sufficient, but using both is consistent.

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 for-2.5 05/12] qjson: Give each of the six structural chars its own token type

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1359 bytes --]

On 11/25/2015 02:23 PM, Markus Armbruster wrote:
> Simplifies things, because we always check for a specific one.
> 
> Signed-off-by: Markus Armbruster <armbru@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(-)

Diffstat shows that it is already a win, even if slight; the real win is
that later patches are easier :)

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

I might have used LBRACE and LBRACKET - but I also acknowledge that UK
spellers think of '()' for 'bracket'.  Your naming is fine (unless you
really want that bikeshed to be chartreuse).

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 for-2.5 06/12] qjson: Inline token_is_keyword() and simplify

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1193 bytes --]

On 11/25/2015 02:23 PM, Markus Armbruster wrote:
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---
>  qobject/json-parser.c | 20 +++++++-------------
>  1 file changed, 7 insertions(+), 13 deletions(-)
> 

>  
> -    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);

Yay - fewer `' in error messages.  (Great back in the day when fonts
rendered them symmetrically, and still useful in m4; but lousy for
pasting into shell code and in modern fonts)

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 for-2.5 07/12] qjson: Inline token_is_escape() and simplify

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1545 bytes --]

On 11/25/2015 02:23 PM, Markus Armbruster wrote:
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---
>  qobject/json-parser.c | 32 +++++++++++++++-----------------
>  1 file changed, 15 insertions(+), 17 deletions(-)
> 

> +    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")) {

Not for this patch, but I'd love to kill our support for "%ld" - it has
behavior that differs between 32-bit and 64-bit platforms, and is
therefore useless for our goal of using fixed-width integer types.

>          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")) {

Not for this patch, but I'd love to kill our support for "%I64d". Isn't
modern mingw friendlier to using POSIX escape sequences in printf()?
I'm assuming mingw is the only reason we have this hold-out?

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 for-2.5 08/12] qjson: replace QString in JSONLexer with GString

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 951 bytes --]

On 11/25/2015 02:23 PM, Markus Armbruster wrote:
> 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>
> ---
>  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(-)
> 

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 for-2.5 09/12] qjson: Convert to parser to recursive descent

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1339 bytes --]

On 11/25/2015 02:23 PM, Markus Armbruster wrote:
> 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: Markus Armbruster <armbru@redhat.com>
> ---
>  qobject/json-parser.c | 165 ++++++++++++++------------------------------------
>  1 file changed, 47 insertions(+), 118 deletions(-)
> 

>  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");

Should we spell that out as 'end of input'?

But that's cosmetic, and doesn't affect correctness of the conversion.

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 for-2.5 10/12] qjson: store tokens in a GQueue

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 702 bytes --]

On 11/25/2015 02:23 PM, Markus Armbruster wrote:
> 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>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 for-2.5 11/12] qjson: surprise, allocating 6 QObjects per token is expensive

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1181 bytes --]

On 11/25/2015 02:23 PM, Markus Armbruster wrote:
> 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>
> ---
>  include/qapi/qmp/json-streamer.h |   7 +++
>  qobject/json-parser.c            | 115 ++++++++++++++++-----------------------
>  qobject/json-streamer.c          |  19 +++----
>  3 files changed, 63 insertions(+), 78 deletions(-)
> 

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 for-2.5 05/12] qjson: Give each of the six structural chars its own token type

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 11/25/2015 02:23 PM, Markus Armbruster wrote:
>> Simplifies things, because we always check for a specific one.
>> 
>> Signed-off-by: Markus Armbruster <armbru@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(-)
>
> Diffstat shows that it is already a win, even if slight; the real win is
> that later patches are easier :)
>
>> 
>> 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,
>
> I might have used LBRACE and LBRACKET - but I also acknowledge that UK
> spellers think of '()' for 'bracket'.  Your naming is fine (unless you
> really want that bikeshed to be chartreuse).

I normally use (parenthesis), [bracket] and {brace} myself, but here I
decided to stick to RFC 7159's wording:

      begin-array     = ws %x5B ws  ; [ left square bracket

      begin-object    = ws %x7B ws  ; { left curly bracket

      end-array       = ws %x5D ws  ; ] right square bracket

      end-object      = ws %x7D ws  ; } right curly bracket

      name-separator  = ws %x3A ws  ; : colon

      value-separator = ws %x2C ws  ; , comma

> Reviewed-by: Eric Blake <eblake@redhat.com>

Thanks!

Re: [Qemu-devel] [PATCH v3 for-2.5 06/12] qjson: Inline token_is_keyword() and simplify

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 11/25/2015 02:23 PM, Markus Armbruster wrote:
>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>> ---
>>  qobject/json-parser.c | 20 +++++++-------------
>>  1 file changed, 7 insertions(+), 13 deletions(-)
>> 
>
>>  
>> -    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);
>
> Yay - fewer `' in error messages.  (Great back in the day when fonts
> rendered them symmetrically, and still useful in m4; but lousy for
> pasting into shell code and in modern fonts)

Perhaps we can some day use the proper U+2018 (LEFT SINGLE QUOTATION
MARK) and U+2019 (RIGHT SINGLE QUOTATION MARK).

> Reviewed-by: Eric Blake <eblake@redhat.com>

Thanks!

Re: [Qemu-devel] [PATCH v3 for-2.5 07/12] qjson: Inline token_is_escape() and simplify

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 11/25/2015 02:23 PM, Markus Armbruster wrote:
>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>> ---
>>  qobject/json-parser.c | 32 +++++++++++++++-----------------
>>  1 file changed, 15 insertions(+), 17 deletions(-)
>> 
>
>> +    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")) {
>
> Not for this patch, but I'd love to kill our support for "%ld" - it has
> behavior that differs between 32-bit and 64-bit platforms, and is
> therefore useless for our goal of using fixed-width integer types.
>
>>          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")) {
>
> Not for this patch, but I'd love to kill our support for "%I64d". Isn't
> modern mingw friendlier to using POSIX escape sequences in printf()?
> I'm assuming mingw is the only reason we have this hold-out?

These escapes are chosen so we can get type checking from gcc via format
attribute.  The code here is somewhat unclean; it should arguably
compare to "%" PRId64, whatever that may be.  Instead, we accept
anything we anticipate it could be.

> Reviewed-by: Eric Blake <eblake@redhat.com>

Thanks!

Re: [Qemu-devel] [PATCH v3 for-2.5 09/12] qjson: Convert to parser to recursive descent

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 11/25/2015 02:23 PM, Markus Armbruster wrote:
>> 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: Markus Armbruster <armbru@redhat.com>
>> ---
>>  qobject/json-parser.c | 165 ++++++++++++++------------------------------------
>>  1 file changed, 47 insertions(+), 118 deletions(-)
>> 
>
>>  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");
>
> Should we spell that out as 'end of input'?
>
> But that's cosmetic, and doesn't affect correctness of the conversion.

Doesn't matter, because we generally throw away these error messages,
then make up a useless one *boggle*.  Once that's fixed, the
parse_error() could use some love.

> Reviewed-by: Eric Blake <eblake@redhat.com>

Thanks!

Re: [Qemu-devel] [PATCH v3 for-2.5 09/12] qjson: Convert to parser to recursive descent

[Markus Armbruster]

Markus Armbruster <armbru@redhat.com> writes:

> 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: Markus Armbruster <armbru@redhat.com>

Missing a
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>

Fixed in my tree.