[Qemu-devel] [PATCH for-1.2 v3 1/3] qlist: add qlist_size()

[Qemu-devel] [PATCH for-1.2 v3 1/3] qlist: add qlist_size()

[Michael Roth]

Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
---
 qlist.c |   13 +++++++++++++
 qlist.h |    1 +
 2 files changed, 14 insertions(+)

diff --git a/qlist.c b/qlist.c
index 88498b1..b48ec5b 100644
--- a/qlist.c
+++ b/qlist.c
@@ -124,6 +124,19 @@ int qlist_empty(const QList *qlist)
     return QTAILQ_EMPTY(&qlist->head);
 }
 
+static void qlist_size_iter(QObject *obj, void *opaque)
+{
+    size_t *count = opaque;
+    (*count)++;
+}
+
+size_t qlist_size(const QList *qlist)
+{
+    size_t count = 0;
+    qlist_iter(qlist, qlist_size_iter, &count);
+    return count;
+}
+
 /**
  * qobject_to_qlist(): Convert a QObject into a QList
  */
diff --git a/qlist.h b/qlist.h
index d426bd4..ae776f9 100644
--- a/qlist.h
+++ b/qlist.h
@@ -49,6 +49,7 @@ void qlist_iter(const QList *qlist,
 QObject *qlist_pop(QList *qlist);
 QObject *qlist_peek(QList *qlist);
 int qlist_empty(const QList *qlist);
+size_t qlist_size(const QList *qlist);
 QList *qobject_to_qlist(const QObject *obj);
 
 static inline const QListEntry *qlist_first(const QList *qlist)
-- 
1.7.9.5

[Qemu-devel] [PATCH for-1.2 v3 2/3] json-parser: don't replicate tokens at each level of recursion

[Michael Roth]

Currently, when parsing a stream of tokens we make a copy of the token
list at the beginning of each level of recursion so that we do not
modify the original list in cases where we need to fall back to an
earlier state.

In the worst case, we will only read 1 or 2 tokens off the list before
recursing again, which means an upper bound of roughly N^2 token allocations.

For a "reasonably" sized QMP request (in this a QMP representation of
cirrus_vga's device state, generated via QIDL, being passed in via
qom-set), this caused my 16GB's of memory to be exhausted before any
noticeable progress was made by the parser.

This patch works around the issue by using single copy of the token list
in the form of an indexable array so that we can save/restore state by
manipulating indices.

A subsequent commit adds a "large_dict" test case which exhibits the
same behavior as above. With this patch applied the test case successfully
completes in under a second.

Tested with valgrind, make check, and QMP.

Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
---
 json-parser.c |  230 +++++++++++++++++++++++++++++++++++----------------------
 1 file changed, 142 insertions(+), 88 deletions(-)

diff --git a/json-parser.c b/json-parser.c
index 849e215..457291b 100644
--- a/json-parser.c
+++ b/json-parser.c
@@ -27,6 +27,11 @@
 typedef struct JSONParserContext
 {
     Error *err;
+    struct {
+        QObject **buf;
+        size_t pos;
+        size_t count;
+    } tokens;
 } JSONParserContext;
 
 #define BUG_ON(cond) assert(!(cond))
@@ -40,7 +45,7 @@ typedef struct JSONParserContext
  * 4) deal with premature EOI
  */
 
-static QObject *parse_value(JSONParserContext *ctxt, QList **tokens, va_list *ap);
+static QObject *parse_value(JSONParserContext *ctxt, va_list *ap);
 
 /**
  * Token manipulators
@@ -270,27 +275,111 @@ out:
     return NULL;
 }
 
+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;
+}
+
+/* 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;
+}
+
+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;
+    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)
+{
+    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;
+
+    return ctxt;
+}
+
+/* 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]);
+        }
+        g_free(ctxt->tokens.buf);
+        g_free(ctxt);
+    }
+}
+
 /**
  * Parsing rules
  */
-static int parse_pair(JSONParserContext *ctxt, QDict *dict, QList **tokens, va_list *ap)
+static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
 {
     QObject *key = NULL, *token = NULL, *value, *peek;
-    QList *working = qlist_copy(*tokens);
+    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
-    peek = qlist_peek(working);
+    peek = parser_context_peek_token(ctxt);
     if (peek == NULL) {
         parse_error(ctxt, NULL, "premature EOI");
         goto out;
     }
 
-    key = parse_value(ctxt, &working, ap);
+    key = parse_value(ctxt, ap);
     if (!key || qobject_type(key) != QTYPE_QSTRING) {
         parse_error(ctxt, peek, "key is not a string in object");
         goto out;
     }
 
-    token = qlist_pop(working);
+    token = parser_context_pop_token(ctxt);
     if (token == NULL) {
         parse_error(ctxt, NULL, "premature EOI");
         goto out;
@@ -301,7 +390,7 @@ static int parse_pair(JSONParserContext *ctxt, QDict *dict, QList **tokens, va_l
         goto out;
     }
 
-    value = parse_value(ctxt, &working, ap);
+    value = parse_value(ctxt, ap);
     if (value == NULL) {
         parse_error(ctxt, token, "Missing value in dict");
         goto out;
@@ -309,28 +398,24 @@ static int parse_pair(JSONParserContext *ctxt, QDict *dict, QList **tokens, va_l
 
     qdict_put_obj(dict, qstring_get_str(qobject_to_qstring(key)), value);
 
-    qobject_decref(token);
     qobject_decref(key);
-    QDECREF(*tokens);
-    *tokens = working;
 
     return 0;
 
 out:
-    qobject_decref(token);
+    parser_context_restore(ctxt, saved_ctxt);
     qobject_decref(key);
-    QDECREF(working);
 
     return -1;
 }
 
-static QObject *parse_object(JSONParserContext *ctxt, QList **tokens, va_list *ap)
+static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
 {
     QDict *dict = NULL;
     QObject *token, *peek;
-    QList *working = qlist_copy(*tokens);
+    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
-    token = qlist_pop(working);
+    token = parser_context_pop_token(ctxt);
     if (token == NULL) {
         goto out;
     }
@@ -338,23 +423,22 @@ static QObject *parse_object(JSONParserContext *ctxt, QList **tokens, va_list *a
     if (!token_is_operator(token, '{')) {
         goto out;
     }
-    qobject_decref(token);
     token = NULL;
 
     dict = qdict_new();
 
-    peek = qlist_peek(working);
+    peek = parser_context_peek_token(ctxt);
     if (peek == NULL) {
         parse_error(ctxt, NULL, "premature EOI");
         goto out;
     }
 
     if (!token_is_operator(peek, '}')) {
-        if (parse_pair(ctxt, dict, &working, ap) == -1) {
+        if (parse_pair(ctxt, dict, ap) == -1) {
             goto out;
         }
 
-        token = qlist_pop(working);
+        token = parser_context_pop_token(ctxt);
         if (token == NULL) {
             parse_error(ctxt, NULL, "premature EOI");
             goto out;
@@ -365,59 +449,52 @@ static QObject *parse_object(JSONParserContext *ctxt, QList **tokens, va_list *a
                 parse_error(ctxt, token, "expected separator in dict");
                 goto out;
             }
-            qobject_decref(token);
             token = NULL;
 
-            if (parse_pair(ctxt, dict, &working, ap) == -1) {
+            if (parse_pair(ctxt, dict, ap) == -1) {
                 goto out;
             }
 
-            token = qlist_pop(working);
+            token = parser_context_pop_token(ctxt);
             if (token == NULL) {
                 parse_error(ctxt, NULL, "premature EOI");
                 goto out;
             }
         }
-        qobject_decref(token);
         token = NULL;
     } else {
-        token = qlist_pop(working);
-        qobject_decref(token);
+        token = parser_context_pop_token(ctxt);
         token = NULL;
     }
 
-    QDECREF(*tokens);
-    *tokens = working;
-
     return QOBJECT(dict);
 
 out:
-    qobject_decref(token);
-    QDECREF(working);
+    parser_context_restore(ctxt, saved_ctxt);
     QDECREF(dict);
     return NULL;
 }
 
-static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap)
+static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
 {
     QList *list = NULL;
     QObject *token, *peek;
-    QList *working = qlist_copy(*tokens);
+    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
-    token = qlist_pop(working);
+    token = parser_context_pop_token(ctxt);
     if (token == NULL) {
         goto out;
     }
 
     if (!token_is_operator(token, '[')) {
+        token = NULL;
         goto out;
     }
-    qobject_decref(token);
     token = NULL;
 
     list = qlist_new();
 
-    peek = qlist_peek(working);
+    peek = parser_context_peek_token(ctxt);
     if (peek == NULL) {
         parse_error(ctxt, NULL, "premature EOI");
         goto out;
@@ -426,7 +503,7 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
     if (!token_is_operator(peek, ']')) {
         QObject *obj;
 
-        obj = parse_value(ctxt, &working, ap);
+        obj = parse_value(ctxt, ap);
         if (obj == NULL) {
             parse_error(ctxt, token, "expecting value");
             goto out;
@@ -434,7 +511,7 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
 
         qlist_append_obj(list, obj);
 
-        token = qlist_pop(working);
+        token = parser_context_pop_token(ctxt);
         if (token == NULL) {
             parse_error(ctxt, NULL, "premature EOI");
             goto out;
@@ -446,10 +523,9 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
                 goto out;
             }
 
-            qobject_decref(token);
             token = NULL;
 
-            obj = parse_value(ctxt, &working, ap);
+            obj = parse_value(ctxt, ap);
             if (obj == NULL) {
                 parse_error(ctxt, token, "expecting value");
                 goto out;
@@ -457,39 +533,33 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
 
             qlist_append_obj(list, obj);
 
-            token = qlist_pop(working);
+            token = parser_context_pop_token(ctxt);
             if (token == NULL) {
                 parse_error(ctxt, NULL, "premature EOI");
                 goto out;
             }
         }
 
-        qobject_decref(token);
         token = NULL;
     } else {
-        token = qlist_pop(working);
-        qobject_decref(token);
+        token = parser_context_pop_token(ctxt);
         token = NULL;
     }
 
-    QDECREF(*tokens);
-    *tokens = working;
-
     return QOBJECT(list);
 
 out:
-    qobject_decref(token);
-    QDECREF(working);
+    parser_context_restore(ctxt, saved_ctxt);
     QDECREF(list);
     return NULL;
 }
 
-static QObject *parse_keyword(JSONParserContext *ctxt, QList **tokens)
+static QObject *parse_keyword(JSONParserContext *ctxt)
 {
     QObject *token, *ret;
-    QList *working = qlist_copy(*tokens);
+    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
-    token = qlist_pop(working);
+    token = parser_context_pop_token(ctxt);
     if (token == NULL) {
         goto out;
     }
@@ -507,29 +577,24 @@ static QObject *parse_keyword(JSONParserContext *ctxt, QList **tokens)
         goto out;
     }
 
-    qobject_decref(token);
-    QDECREF(*tokens);
-    *tokens = working;
-
     return ret;
 
 out: 
-    qobject_decref(token);
-    QDECREF(working);
+    parser_context_restore(ctxt, saved_ctxt);
 
     return NULL;
 }
 
-static QObject *parse_escape(JSONParserContext *ctxt, QList **tokens, va_list *ap)
+static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)
 {
     QObject *token = NULL, *obj;
-    QList *working = qlist_copy(*tokens);
+    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
     if (ap == NULL) {
         goto out;
     }
 
-    token = qlist_pop(working);
+    token = parser_context_pop_token(ctxt);
     if (token == NULL) {
         goto out;
     }
@@ -553,25 +618,20 @@ static QObject *parse_escape(JSONParserContext *ctxt, QList **tokens, va_list *a
         goto out;
     }
 
-    qobject_decref(token);
-    QDECREF(*tokens);
-    *tokens = working;
-
     return obj;
 
 out:
-    qobject_decref(token);
-    QDECREF(working);
+    parser_context_restore(ctxt, saved_ctxt);
 
     return NULL;
 }
 
-static QObject *parse_literal(JSONParserContext *ctxt, QList **tokens)
+static QObject *parse_literal(JSONParserContext *ctxt)
 {
     QObject *token, *obj;
-    QList *working = qlist_copy(*tokens);
+    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
-    token = qlist_pop(working);
+    token = parser_context_pop_token(ctxt);
     if (token == NULL) {
         goto out;
     }
@@ -591,35 +651,30 @@ static QObject *parse_literal(JSONParserContext *ctxt, QList **tokens)
         goto out;
     }
 
-    qobject_decref(token);
-    QDECREF(*tokens);
-    *tokens = working;
-
     return obj;
 
 out:
-    qobject_decref(token);
-    QDECREF(working);
+    parser_context_restore(ctxt, saved_ctxt);
 
     return NULL;
 }
 
-static QObject *parse_value(JSONParserContext *ctxt, QList **tokens, va_list *ap)
+static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
 {
     QObject *obj;
 
-    obj = parse_object(ctxt, tokens, ap);
+    obj = parse_object(ctxt, ap);
     if (obj == NULL) {
-        obj = parse_array(ctxt, tokens, ap);
+        obj = parse_array(ctxt, ap);
     }
     if (obj == NULL) {
-        obj = parse_escape(ctxt, tokens, ap);
+        obj = parse_escape(ctxt, ap);
     }
     if (obj == NULL) {
-        obj = parse_keyword(ctxt, tokens);
+        obj = parse_keyword(ctxt);
     } 
     if (obj == NULL) {
-        obj = parse_literal(ctxt, tokens);
+        obj = parse_literal(ctxt);
     }
 
     return obj;
@@ -632,19 +687,18 @@ QObject *json_parser_parse(QList *tokens, va_list *ap)
 
 QObject *json_parser_parse_err(QList *tokens, va_list *ap, Error **errp)
 {
-    JSONParserContext ctxt = {};
-    QList *working;
+    JSONParserContext *ctxt = parser_context_new(tokens);
     QObject *result;
 
-    if (!tokens) {
+    if (!ctxt) {
         return NULL;
     }
-    working = qlist_copy(tokens);
-    result = parse_value(&ctxt, &working, ap);
 
-    QDECREF(working);
+    result = parse_value(ctxt, ap);
+
+    error_propagate(errp, ctxt->err);
 
-    error_propagate(errp, ctxt.err);
+    parser_context_free(ctxt);
 
     return result;
 }
-- 
1.7.9.5

Re: [Qemu-devel] [PATCH for-1.2 v3 2/3] json-parser: don't replicate tokens at each level of recursion

[Eric Blake]

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

On 08/15/2012 12:45 PM, Michael Roth wrote:
> Currently, when parsing a stream of tokens we make a copy of the token
> list at the beginning of each level of recursion so that we do not
> modify the original list in cases where we need to fall back to an
> earlier state.
> 
> In the worst case, we will only read 1 or 2 tokens off the list before
> recursing again, which means an upper bound of roughly N^2 token allocations.
> 
> For a "reasonably" sized QMP request (in this a QMP representation of
> cirrus_vga's device state, generated via QIDL, being passed in via
> qom-set), this caused my 16GB's of memory to be exhausted before any
> noticeable progress was made by the parser.
> 
> This patch works around the issue by using single copy of the token list
> in the form of an indexable array so that we can save/restore state by
> manipulating indices.
> 
> A subsequent commit adds a "large_dict" test case which exhibits the
> same behavior as above. With this patch applied the test case successfully
> completes in under a second.
> 
> Tested with valgrind, make check, and QMP.
> 
> Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
> ---
>  json-parser.c |  230 +++++++++++++++++++++++++++++++++++----------------------
>  1 file changed, 142 insertions(+), 88 deletions(-)

I'm not the most familiar with this code, so take my review with a grain
of salt, but I read through it and the transformation looks sane (and my
non-code findings from v2 were fixed).

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

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

Is it any simpler to condense 3 lines to 1:

saved_cts.tokens = ctxt->tokens;

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

and again, ctxt->tokens = saved_ctxt.tokens;

-- 
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: 620 bytes --]

Re: [Qemu-devel] [PATCH for-1.2 v3 2/3] json-parser: don't replicate tokens at each level of recursion

[Michael Roth]

On Wed, Aug 15, 2012 at 02:04:52PM -0600, Eric Blake wrote:
> On 08/15/2012 12:45 PM, Michael Roth wrote:
> > Currently, when parsing a stream of tokens we make a copy of the token
> > list at the beginning of each level of recursion so that we do not
> > modify the original list in cases where we need to fall back to an
> > earlier state.
> > 
> > In the worst case, we will only read 1 or 2 tokens off the list before
> > recursing again, which means an upper bound of roughly N^2 token allocations.
> > 
> > For a "reasonably" sized QMP request (in this a QMP representation of
> > cirrus_vga's device state, generated via QIDL, being passed in via
> > qom-set), this caused my 16GB's of memory to be exhausted before any
> > noticeable progress was made by the parser.
> > 
> > This patch works around the issue by using single copy of the token list
> > in the form of an indexable array so that we can save/restore state by
> > manipulating indices.
> > 
> > A subsequent commit adds a "large_dict" test case which exhibits the
> > same behavior as above. With this patch applied the test case successfully
> > completes in under a second.
> > 
> > Tested with valgrind, make check, and QMP.
> > 
> > Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
> > ---
> >  json-parser.c |  230 +++++++++++++++++++++++++++++++++++----------------------
> >  1 file changed, 142 insertions(+), 88 deletions(-)
> 
> I'm not the most familiar with this code, so take my review with a grain
> of salt, but I read through it and the transformation looks sane (and my
> non-code findings from v2 were fixed).
> 
> Reviewed-by: Eric Blake <eblake@redhat.com>
> 
> > +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;
> 
> Is it any simpler to condense 3 lines to 1:
> 
> saved_cts.tokens = ctxt->tokens;
> 
> > +    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;
> 
> and again, ctxt->tokens = saved_ctxt.tokens;

Poor function naming: save/restore apply to the token state, the other
fields in ctxt are unused, so I opted to set the fields explicitly.

Can probably make this read a little better by breaking token state off
into it's own struct, but I think we can clean that up later.

Thanks for the review!

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

Re: [Qemu-devel] [PATCH for-1.2 v3 2/3] json-parser: don't replicate tokens at each level of recursion

[Luiz Capitulino]

On Wed, 15 Aug 2012 13:45:43 -0500
Michael Roth <mdroth@linux.vnet.ibm.com> wrote:

> Currently, when parsing a stream of tokens we make a copy of the token
> list at the beginning of each level of recursion so that we do not
> modify the original list in cases where we need to fall back to an
> earlier state.
> 
> In the worst case, we will only read 1 or 2 tokens off the list before
> recursing again, which means an upper bound of roughly N^2 token allocations.
> 
> For a "reasonably" sized QMP request (in this a QMP representation of
> cirrus_vga's device state, generated via QIDL, being passed in via
> qom-set), this caused my 16GB's of memory to be exhausted before any
> noticeable progress was made by the parser.
> 
> This patch works around the issue by using single copy of the token list
> in the form of an indexable array so that we can save/restore state by
> manipulating indices.
> 
> A subsequent commit adds a "large_dict" test case which exhibits the
> same behavior as above. With this patch applied the test case successfully
> completes in under a second.
> 
> Tested with valgrind, make check, and QMP.
> 
> Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
> ---
>  json-parser.c |  230 +++++++++++++++++++++++++++++++++++----------------------
>  1 file changed, 142 insertions(+), 88 deletions(-)
> 
> diff --git a/json-parser.c b/json-parser.c
> index 849e215..457291b 100644
> --- a/json-parser.c
> +++ b/json-parser.c
> @@ -27,6 +27,11 @@
>  typedef struct JSONParserContext
>  {
>      Error *err;
> +    struct {
> +        QObject **buf;
> +        size_t pos;
> +        size_t count;
> +    } tokens;
>  } JSONParserContext;
>  
>  #define BUG_ON(cond) assert(!(cond))
> @@ -40,7 +45,7 @@ typedef struct JSONParserContext
>   * 4) deal with premature EOI
>   */
>  
> -static QObject *parse_value(JSONParserContext *ctxt, QList **tokens, va_list *ap);
> +static QObject *parse_value(JSONParserContext *ctxt, va_list *ap);
>  
>  /**
>   * Token manipulators
> @@ -270,27 +275,111 @@ out:
>      return NULL;
>  }
>  
> +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++;

Shouldn't pos be decremented instead? Haven't tried it yet to confirm, but
if I'm right I can fix it myself (unless this requires fixes in other areas).

> +    return token;
> +}
> +
> +/* 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;
> +}
> +
> +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;
> +    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)
> +{
> +    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;
> +
> +    return ctxt;
> +}
> +
> +/* 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]);
> +        }
> +        g_free(ctxt->tokens.buf);
> +        g_free(ctxt);
> +    }
> +}
> +
>  /**
>   * Parsing rules
>   */
> -static int parse_pair(JSONParserContext *ctxt, QDict *dict, QList **tokens, va_list *ap)
> +static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
>  {
>      QObject *key = NULL, *token = NULL, *value, *peek;
> -    QList *working = qlist_copy(*tokens);
> +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
>  
> -    peek = qlist_peek(working);
> +    peek = parser_context_peek_token(ctxt);
>      if (peek == NULL) {
>          parse_error(ctxt, NULL, "premature EOI");
>          goto out;
>      }
>  
> -    key = parse_value(ctxt, &working, ap);
> +    key = parse_value(ctxt, ap);
>      if (!key || qobject_type(key) != QTYPE_QSTRING) {
>          parse_error(ctxt, peek, "key is not a string in object");
>          goto out;
>      }
>  
> -    token = qlist_pop(working);
> +    token = parser_context_pop_token(ctxt);
>      if (token == NULL) {
>          parse_error(ctxt, NULL, "premature EOI");
>          goto out;
> @@ -301,7 +390,7 @@ static int parse_pair(JSONParserContext *ctxt, QDict *dict, QList **tokens, va_l
>          goto out;
>      }
>  
> -    value = parse_value(ctxt, &working, ap);
> +    value = parse_value(ctxt, ap);
>      if (value == NULL) {
>          parse_error(ctxt, token, "Missing value in dict");
>          goto out;
> @@ -309,28 +398,24 @@ static int parse_pair(JSONParserContext *ctxt, QDict *dict, QList **tokens, va_l
>  
>      qdict_put_obj(dict, qstring_get_str(qobject_to_qstring(key)), value);
>  
> -    qobject_decref(token);
>      qobject_decref(key);
> -    QDECREF(*tokens);
> -    *tokens = working;
>  
>      return 0;
>  
>  out:
> -    qobject_decref(token);
> +    parser_context_restore(ctxt, saved_ctxt);
>      qobject_decref(key);
> -    QDECREF(working);
>  
>      return -1;
>  }
>  
> -static QObject *parse_object(JSONParserContext *ctxt, QList **tokens, va_list *ap)
> +static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
>  {
>      QDict *dict = NULL;
>      QObject *token, *peek;
> -    QList *working = qlist_copy(*tokens);
> +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
>  
> -    token = qlist_pop(working);
> +    token = parser_context_pop_token(ctxt);
>      if (token == NULL) {
>          goto out;
>      }
> @@ -338,23 +423,22 @@ static QObject *parse_object(JSONParserContext *ctxt, QList **tokens, va_list *a
>      if (!token_is_operator(token, '{')) {
>          goto out;
>      }
> -    qobject_decref(token);
>      token = NULL;
>  
>      dict = qdict_new();
>  
> -    peek = qlist_peek(working);
> +    peek = parser_context_peek_token(ctxt);
>      if (peek == NULL) {
>          parse_error(ctxt, NULL, "premature EOI");
>          goto out;
>      }
>  
>      if (!token_is_operator(peek, '}')) {
> -        if (parse_pair(ctxt, dict, &working, ap) == -1) {
> +        if (parse_pair(ctxt, dict, ap) == -1) {
>              goto out;
>          }
>  
> -        token = qlist_pop(working);
> +        token = parser_context_pop_token(ctxt);
>          if (token == NULL) {
>              parse_error(ctxt, NULL, "premature EOI");
>              goto out;
> @@ -365,59 +449,52 @@ static QObject *parse_object(JSONParserContext *ctxt, QList **tokens, va_list *a
>                  parse_error(ctxt, token, "expected separator in dict");
>                  goto out;
>              }
> -            qobject_decref(token);
>              token = NULL;
>  
> -            if (parse_pair(ctxt, dict, &working, ap) == -1) {
> +            if (parse_pair(ctxt, dict, ap) == -1) {
>                  goto out;
>              }
>  
> -            token = qlist_pop(working);
> +            token = parser_context_pop_token(ctxt);
>              if (token == NULL) {
>                  parse_error(ctxt, NULL, "premature EOI");
>                  goto out;
>              }
>          }
> -        qobject_decref(token);
>          token = NULL;
>      } else {
> -        token = qlist_pop(working);
> -        qobject_decref(token);
> +        token = parser_context_pop_token(ctxt);
>          token = NULL;
>      }
>  
> -    QDECREF(*tokens);
> -    *tokens = working;
> -
>      return QOBJECT(dict);
>  
>  out:
> -    qobject_decref(token);
> -    QDECREF(working);
> +    parser_context_restore(ctxt, saved_ctxt);
>      QDECREF(dict);
>      return NULL;
>  }
>  
> -static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap)
> +static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
>  {
>      QList *list = NULL;
>      QObject *token, *peek;
> -    QList *working = qlist_copy(*tokens);
> +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
>  
> -    token = qlist_pop(working);
> +    token = parser_context_pop_token(ctxt);
>      if (token == NULL) {
>          goto out;
>      }
>  
>      if (!token_is_operator(token, '[')) {
> +        token = NULL;
>          goto out;
>      }
> -    qobject_decref(token);
>      token = NULL;
>  
>      list = qlist_new();
>  
> -    peek = qlist_peek(working);
> +    peek = parser_context_peek_token(ctxt);
>      if (peek == NULL) {
>          parse_error(ctxt, NULL, "premature EOI");
>          goto out;
> @@ -426,7 +503,7 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
>      if (!token_is_operator(peek, ']')) {
>          QObject *obj;
>  
> -        obj = parse_value(ctxt, &working, ap);
> +        obj = parse_value(ctxt, ap);
>          if (obj == NULL) {
>              parse_error(ctxt, token, "expecting value");
>              goto out;
> @@ -434,7 +511,7 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
>  
>          qlist_append_obj(list, obj);
>  
> -        token = qlist_pop(working);
> +        token = parser_context_pop_token(ctxt);
>          if (token == NULL) {
>              parse_error(ctxt, NULL, "premature EOI");
>              goto out;
> @@ -446,10 +523,9 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
>                  goto out;
>              }
>  
> -            qobject_decref(token);
>              token = NULL;
>  
> -            obj = parse_value(ctxt, &working, ap);
> +            obj = parse_value(ctxt, ap);
>              if (obj == NULL) {
>                  parse_error(ctxt, token, "expecting value");
>                  goto out;
> @@ -457,39 +533,33 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
>  
>              qlist_append_obj(list, obj);
>  
> -            token = qlist_pop(working);
> +            token = parser_context_pop_token(ctxt);
>              if (token == NULL) {
>                  parse_error(ctxt, NULL, "premature EOI");
>                  goto out;
>              }
>          }
>  
> -        qobject_decref(token);
>          token = NULL;
>      } else {
> -        token = qlist_pop(working);
> -        qobject_decref(token);
> +        token = parser_context_pop_token(ctxt);
>          token = NULL;
>      }
>  
> -    QDECREF(*tokens);
> -    *tokens = working;
> -
>      return QOBJECT(list);
>  
>  out:
> -    qobject_decref(token);
> -    QDECREF(working);
> +    parser_context_restore(ctxt, saved_ctxt);
>      QDECREF(list);
>      return NULL;
>  }
>  
> -static QObject *parse_keyword(JSONParserContext *ctxt, QList **tokens)
> +static QObject *parse_keyword(JSONParserContext *ctxt)
>  {
>      QObject *token, *ret;
> -    QList *working = qlist_copy(*tokens);
> +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
>  
> -    token = qlist_pop(working);
> +    token = parser_context_pop_token(ctxt);
>      if (token == NULL) {
>          goto out;
>      }
> @@ -507,29 +577,24 @@ static QObject *parse_keyword(JSONParserContext *ctxt, QList **tokens)
>          goto out;
>      }
>  
> -    qobject_decref(token);
> -    QDECREF(*tokens);
> -    *tokens = working;
> -
>      return ret;
>  
>  out: 
> -    qobject_decref(token);
> -    QDECREF(working);
> +    parser_context_restore(ctxt, saved_ctxt);
>  
>      return NULL;
>  }
>  
> -static QObject *parse_escape(JSONParserContext *ctxt, QList **tokens, va_list *ap)
> +static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)
>  {
>      QObject *token = NULL, *obj;
> -    QList *working = qlist_copy(*tokens);
> +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
>  
>      if (ap == NULL) {
>          goto out;
>      }
>  
> -    token = qlist_pop(working);
> +    token = parser_context_pop_token(ctxt);
>      if (token == NULL) {
>          goto out;
>      }
> @@ -553,25 +618,20 @@ static QObject *parse_escape(JSONParserContext *ctxt, QList **tokens, va_list *a
>          goto out;
>      }
>  
> -    qobject_decref(token);
> -    QDECREF(*tokens);
> -    *tokens = working;
> -
>      return obj;
>  
>  out:
> -    qobject_decref(token);
> -    QDECREF(working);
> +    parser_context_restore(ctxt, saved_ctxt);
>  
>      return NULL;
>  }
>  
> -static QObject *parse_literal(JSONParserContext *ctxt, QList **tokens)
> +static QObject *parse_literal(JSONParserContext *ctxt)
>  {
>      QObject *token, *obj;
> -    QList *working = qlist_copy(*tokens);
> +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
>  
> -    token = qlist_pop(working);
> +    token = parser_context_pop_token(ctxt);
>      if (token == NULL) {
>          goto out;
>      }
> @@ -591,35 +651,30 @@ static QObject *parse_literal(JSONParserContext *ctxt, QList **tokens)
>          goto out;
>      }
>  
> -    qobject_decref(token);
> -    QDECREF(*tokens);
> -    *tokens = working;
> -
>      return obj;
>  
>  out:
> -    qobject_decref(token);
> -    QDECREF(working);
> +    parser_context_restore(ctxt, saved_ctxt);
>  
>      return NULL;
>  }
>  
> -static QObject *parse_value(JSONParserContext *ctxt, QList **tokens, va_list *ap)
> +static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
>  {
>      QObject *obj;
>  
> -    obj = parse_object(ctxt, tokens, ap);
> +    obj = parse_object(ctxt, ap);
>      if (obj == NULL) {
> -        obj = parse_array(ctxt, tokens, ap);
> +        obj = parse_array(ctxt, ap);
>      }
>      if (obj == NULL) {
> -        obj = parse_escape(ctxt, tokens, ap);
> +        obj = parse_escape(ctxt, ap);
>      }
>      if (obj == NULL) {
> -        obj = parse_keyword(ctxt, tokens);
> +        obj = parse_keyword(ctxt);
>      } 
>      if (obj == NULL) {
> -        obj = parse_literal(ctxt, tokens);
> +        obj = parse_literal(ctxt);
>      }
>  
>      return obj;
> @@ -632,19 +687,18 @@ QObject *json_parser_parse(QList *tokens, va_list *ap)
>  
>  QObject *json_parser_parse_err(QList *tokens, va_list *ap, Error **errp)
>  {
> -    JSONParserContext ctxt = {};
> -    QList *working;
> +    JSONParserContext *ctxt = parser_context_new(tokens);
>      QObject *result;
>  
> -    if (!tokens) {
> +    if (!ctxt) {
>          return NULL;
>      }
> -    working = qlist_copy(tokens);
> -    result = parse_value(&ctxt, &working, ap);
>  
> -    QDECREF(working);
> +    result = parse_value(ctxt, ap);
> +
> +    error_propagate(errp, ctxt->err);
>  
> -    error_propagate(errp, ctxt.err);
> +    parser_context_free(ctxt);
>  
>      return result;
>  }

Re: [Qemu-devel] [PATCH for-1.2 v3 2/3] json-parser: don't replicate tokens at each level of recursion

[Michael Roth]

On Thu, Aug 16, 2012 at 11:11:26AM -0300, Luiz Capitulino wrote:
> On Wed, 15 Aug 2012 13:45:43 -0500
> Michael Roth <mdroth@linux.vnet.ibm.com> wrote:
> 
> > Currently, when parsing a stream of tokens we make a copy of the token
> > list at the beginning of each level of recursion so that we do not
> > modify the original list in cases where we need to fall back to an
> > earlier state.
> > 
> > In the worst case, we will only read 1 or 2 tokens off the list before
> > recursing again, which means an upper bound of roughly N^2 token allocations.
> > 
> > For a "reasonably" sized QMP request (in this a QMP representation of
> > cirrus_vga's device state, generated via QIDL, being passed in via
> > qom-set), this caused my 16GB's of memory to be exhausted before any
> > noticeable progress was made by the parser.
> > 
> > This patch works around the issue by using single copy of the token list
> > in the form of an indexable array so that we can save/restore state by
> > manipulating indices.
> > 
> > A subsequent commit adds a "large_dict" test case which exhibits the
> > same behavior as above. With this patch applied the test case successfully
> > completes in under a second.
> > 
> > Tested with valgrind, make check, and QMP.
> > 
> > Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
> > ---
> >  json-parser.c |  230 +++++++++++++++++++++++++++++++++++----------------------
> >  1 file changed, 142 insertions(+), 88 deletions(-)
> > 
> > diff --git a/json-parser.c b/json-parser.c
> > index 849e215..457291b 100644
> > --- a/json-parser.c
> > +++ b/json-parser.c
> > @@ -27,6 +27,11 @@
> >  typedef struct JSONParserContext
> >  {
> >      Error *err;
> > +    struct {
> > +        QObject **buf;
> > +        size_t pos;
> > +        size_t count;
> > +    } tokens;
> >  } JSONParserContext;
> >  
> >  #define BUG_ON(cond) assert(!(cond))
> > @@ -40,7 +45,7 @@ typedef struct JSONParserContext
> >   * 4) deal with premature EOI
> >   */
> >  
> > -static QObject *parse_value(JSONParserContext *ctxt, QList **tokens, va_list *ap);
> > +static QObject *parse_value(JSONParserContext *ctxt, va_list *ap);
> >  
> >  /**
> >   * Token manipulators
> > @@ -270,27 +275,111 @@ out:
> >      return NULL;
> >  }
> >  
> > +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++;
> 
> Shouldn't pos be decremented instead? Haven't tried it yet to confirm, but
> if I'm right I can fix it myself (unless this requires fixes in other areas).
> 

No that's intentional, since qlist_pop() (which this replaces) actually "pops"
from the beginning of the list. So in this case we make the next element the
new "head" by simply incrementing the starting position (so it's easy to roll
back later).

> > +    return token;
> > +}
> > +
> > +/* 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;
> > +}
> > +
> > +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;
> > +    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)
> > +{
> > +    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;
> > +
> > +    return ctxt;
> > +}
> > +
> > +/* 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]);
> > +        }
> > +        g_free(ctxt->tokens.buf);
> > +        g_free(ctxt);
> > +    }
> > +}
> > +
> >  /**
> >   * Parsing rules
> >   */
> > -static int parse_pair(JSONParserContext *ctxt, QDict *dict, QList **tokens, va_list *ap)
> > +static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
> >  {
> >      QObject *key = NULL, *token = NULL, *value, *peek;
> > -    QList *working = qlist_copy(*tokens);
> > +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
> >  
> > -    peek = qlist_peek(working);
> > +    peek = parser_context_peek_token(ctxt);
> >      if (peek == NULL) {
> >          parse_error(ctxt, NULL, "premature EOI");
> >          goto out;
> >      }
> >  
> > -    key = parse_value(ctxt, &working, ap);
> > +    key = parse_value(ctxt, ap);
> >      if (!key || qobject_type(key) != QTYPE_QSTRING) {
> >          parse_error(ctxt, peek, "key is not a string in object");
> >          goto out;
> >      }
> >  
> > -    token = qlist_pop(working);
> > +    token = parser_context_pop_token(ctxt);
> >      if (token == NULL) {
> >          parse_error(ctxt, NULL, "premature EOI");
> >          goto out;
> > @@ -301,7 +390,7 @@ static int parse_pair(JSONParserContext *ctxt, QDict *dict, QList **tokens, va_l
> >          goto out;
> >      }
> >  
> > -    value = parse_value(ctxt, &working, ap);
> > +    value = parse_value(ctxt, ap);
> >      if (value == NULL) {
> >          parse_error(ctxt, token, "Missing value in dict");
> >          goto out;
> > @@ -309,28 +398,24 @@ static int parse_pair(JSONParserContext *ctxt, QDict *dict, QList **tokens, va_l
> >  
> >      qdict_put_obj(dict, qstring_get_str(qobject_to_qstring(key)), value);
> >  
> > -    qobject_decref(token);
> >      qobject_decref(key);
> > -    QDECREF(*tokens);
> > -    *tokens = working;
> >  
> >      return 0;
> >  
> >  out:
> > -    qobject_decref(token);
> > +    parser_context_restore(ctxt, saved_ctxt);
> >      qobject_decref(key);
> > -    QDECREF(working);
> >  
> >      return -1;
> >  }
> >  
> > -static QObject *parse_object(JSONParserContext *ctxt, QList **tokens, va_list *ap)
> > +static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
> >  {
> >      QDict *dict = NULL;
> >      QObject *token, *peek;
> > -    QList *working = qlist_copy(*tokens);
> > +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
> >  
> > -    token = qlist_pop(working);
> > +    token = parser_context_pop_token(ctxt);
> >      if (token == NULL) {
> >          goto out;
> >      }
> > @@ -338,23 +423,22 @@ static QObject *parse_object(JSONParserContext *ctxt, QList **tokens, va_list *a
> >      if (!token_is_operator(token, '{')) {
> >          goto out;
> >      }
> > -    qobject_decref(token);
> >      token = NULL;
> >  
> >      dict = qdict_new();
> >  
> > -    peek = qlist_peek(working);
> > +    peek = parser_context_peek_token(ctxt);
> >      if (peek == NULL) {
> >          parse_error(ctxt, NULL, "premature EOI");
> >          goto out;
> >      }
> >  
> >      if (!token_is_operator(peek, '}')) {
> > -        if (parse_pair(ctxt, dict, &working, ap) == -1) {
> > +        if (parse_pair(ctxt, dict, ap) == -1) {
> >              goto out;
> >          }
> >  
> > -        token = qlist_pop(working);
> > +        token = parser_context_pop_token(ctxt);
> >          if (token == NULL) {
> >              parse_error(ctxt, NULL, "premature EOI");
> >              goto out;
> > @@ -365,59 +449,52 @@ static QObject *parse_object(JSONParserContext *ctxt, QList **tokens, va_list *a
> >                  parse_error(ctxt, token, "expected separator in dict");
> >                  goto out;
> >              }
> > -            qobject_decref(token);
> >              token = NULL;
> >  
> > -            if (parse_pair(ctxt, dict, &working, ap) == -1) {
> > +            if (parse_pair(ctxt, dict, ap) == -1) {
> >                  goto out;
> >              }
> >  
> > -            token = qlist_pop(working);
> > +            token = parser_context_pop_token(ctxt);
> >              if (token == NULL) {
> >                  parse_error(ctxt, NULL, "premature EOI");
> >                  goto out;
> >              }
> >          }
> > -        qobject_decref(token);
> >          token = NULL;
> >      } else {
> > -        token = qlist_pop(working);
> > -        qobject_decref(token);
> > +        token = parser_context_pop_token(ctxt);
> >          token = NULL;
> >      }
> >  
> > -    QDECREF(*tokens);
> > -    *tokens = working;
> > -
> >      return QOBJECT(dict);
> >  
> >  out:
> > -    qobject_decref(token);
> > -    QDECREF(working);
> > +    parser_context_restore(ctxt, saved_ctxt);
> >      QDECREF(dict);
> >      return NULL;
> >  }
> >  
> > -static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap)
> > +static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
> >  {
> >      QList *list = NULL;
> >      QObject *token, *peek;
> > -    QList *working = qlist_copy(*tokens);
> > +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
> >  
> > -    token = qlist_pop(working);
> > +    token = parser_context_pop_token(ctxt);
> >      if (token == NULL) {
> >          goto out;
> >      }
> >  
> >      if (!token_is_operator(token, '[')) {
> > +        token = NULL;
> >          goto out;
> >      }
> > -    qobject_decref(token);
> >      token = NULL;
> >  
> >      list = qlist_new();
> >  
> > -    peek = qlist_peek(working);
> > +    peek = parser_context_peek_token(ctxt);
> >      if (peek == NULL) {
> >          parse_error(ctxt, NULL, "premature EOI");
> >          goto out;
> > @@ -426,7 +503,7 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
> >      if (!token_is_operator(peek, ']')) {
> >          QObject *obj;
> >  
> > -        obj = parse_value(ctxt, &working, ap);
> > +        obj = parse_value(ctxt, ap);
> >          if (obj == NULL) {
> >              parse_error(ctxt, token, "expecting value");
> >              goto out;
> > @@ -434,7 +511,7 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
> >  
> >          qlist_append_obj(list, obj);
> >  
> > -        token = qlist_pop(working);
> > +        token = parser_context_pop_token(ctxt);
> >          if (token == NULL) {
> >              parse_error(ctxt, NULL, "premature EOI");
> >              goto out;
> > @@ -446,10 +523,9 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
> >                  goto out;
> >              }
> >  
> > -            qobject_decref(token);
> >              token = NULL;
> >  
> > -            obj = parse_value(ctxt, &working, ap);
> > +            obj = parse_value(ctxt, ap);
> >              if (obj == NULL) {
> >                  parse_error(ctxt, token, "expecting value");
> >                  goto out;
> > @@ -457,39 +533,33 @@ static QObject *parse_array(JSONParserContext *ctxt, QList **tokens, va_list *ap
> >  
> >              qlist_append_obj(list, obj);
> >  
> > -            token = qlist_pop(working);
> > +            token = parser_context_pop_token(ctxt);
> >              if (token == NULL) {
> >                  parse_error(ctxt, NULL, "premature EOI");
> >                  goto out;
> >              }
> >          }
> >  
> > -        qobject_decref(token);
> >          token = NULL;
> >      } else {
> > -        token = qlist_pop(working);
> > -        qobject_decref(token);
> > +        token = parser_context_pop_token(ctxt);
> >          token = NULL;
> >      }
> >  
> > -    QDECREF(*tokens);
> > -    *tokens = working;
> > -
> >      return QOBJECT(list);
> >  
> >  out:
> > -    qobject_decref(token);
> > -    QDECREF(working);
> > +    parser_context_restore(ctxt, saved_ctxt);
> >      QDECREF(list);
> >      return NULL;
> >  }
> >  
> > -static QObject *parse_keyword(JSONParserContext *ctxt, QList **tokens)
> > +static QObject *parse_keyword(JSONParserContext *ctxt)
> >  {
> >      QObject *token, *ret;
> > -    QList *working = qlist_copy(*tokens);
> > +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
> >  
> > -    token = qlist_pop(working);
> > +    token = parser_context_pop_token(ctxt);
> >      if (token == NULL) {
> >          goto out;
> >      }
> > @@ -507,29 +577,24 @@ static QObject *parse_keyword(JSONParserContext *ctxt, QList **tokens)
> >          goto out;
> >      }
> >  
> > -    qobject_decref(token);
> > -    QDECREF(*tokens);
> > -    *tokens = working;
> > -
> >      return ret;
> >  
> >  out: 
> > -    qobject_decref(token);
> > -    QDECREF(working);
> > +    parser_context_restore(ctxt, saved_ctxt);
> >  
> >      return NULL;
> >  }
> >  
> > -static QObject *parse_escape(JSONParserContext *ctxt, QList **tokens, va_list *ap)
> > +static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)
> >  {
> >      QObject *token = NULL, *obj;
> > -    QList *working = qlist_copy(*tokens);
> > +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
> >  
> >      if (ap == NULL) {
> >          goto out;
> >      }
> >  
> > -    token = qlist_pop(working);
> > +    token = parser_context_pop_token(ctxt);
> >      if (token == NULL) {
> >          goto out;
> >      }
> > @@ -553,25 +618,20 @@ static QObject *parse_escape(JSONParserContext *ctxt, QList **tokens, va_list *a
> >          goto out;
> >      }
> >  
> > -    qobject_decref(token);
> > -    QDECREF(*tokens);
> > -    *tokens = working;
> > -
> >      return obj;
> >  
> >  out:
> > -    qobject_decref(token);
> > -    QDECREF(working);
> > +    parser_context_restore(ctxt, saved_ctxt);
> >  
> >      return NULL;
> >  }
> >  
> > -static QObject *parse_literal(JSONParserContext *ctxt, QList **tokens)
> > +static QObject *parse_literal(JSONParserContext *ctxt)
> >  {
> >      QObject *token, *obj;
> > -    QList *working = qlist_copy(*tokens);
> > +    JSONParserContext saved_ctxt = parser_context_save(ctxt);
> >  
> > -    token = qlist_pop(working);
> > +    token = parser_context_pop_token(ctxt);
> >      if (token == NULL) {
> >          goto out;
> >      }
> > @@ -591,35 +651,30 @@ static QObject *parse_literal(JSONParserContext *ctxt, QList **tokens)
> >          goto out;
> >      }
> >  
> > -    qobject_decref(token);
> > -    QDECREF(*tokens);
> > -    *tokens = working;
> > -
> >      return obj;
> >  
> >  out:
> > -    qobject_decref(token);
> > -    QDECREF(working);
> > +    parser_context_restore(ctxt, saved_ctxt);
> >  
> >      return NULL;
> >  }
> >  
> > -static QObject *parse_value(JSONParserContext *ctxt, QList **tokens, va_list *ap)
> > +static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
> >  {
> >      QObject *obj;
> >  
> > -    obj = parse_object(ctxt, tokens, ap);
> > +    obj = parse_object(ctxt, ap);
> >      if (obj == NULL) {
> > -        obj = parse_array(ctxt, tokens, ap);
> > +        obj = parse_array(ctxt, ap);
> >      }
> >      if (obj == NULL) {
> > -        obj = parse_escape(ctxt, tokens, ap);
> > +        obj = parse_escape(ctxt, ap);
> >      }
> >      if (obj == NULL) {
> > -        obj = parse_keyword(ctxt, tokens);
> > +        obj = parse_keyword(ctxt);
> >      } 
> >      if (obj == NULL) {
> > -        obj = parse_literal(ctxt, tokens);
> > +        obj = parse_literal(ctxt);
> >      }
> >  
> >      return obj;
> > @@ -632,19 +687,18 @@ QObject *json_parser_parse(QList *tokens, va_list *ap)
> >  
> >  QObject *json_parser_parse_err(QList *tokens, va_list *ap, Error **errp)
> >  {
> > -    JSONParserContext ctxt = {};
> > -    QList *working;
> > +    JSONParserContext *ctxt = parser_context_new(tokens);
> >      QObject *result;
> >  
> > -    if (!tokens) {
> > +    if (!ctxt) {
> >          return NULL;
> >      }
> > -    working = qlist_copy(tokens);
> > -    result = parse_value(&ctxt, &working, ap);
> >  
> > -    QDECREF(working);
> > +    result = parse_value(ctxt, ap);
> > +
> > +    error_propagate(errp, ctxt->err);
> >  
> > -    error_propagate(errp, ctxt.err);
> > +    parser_context_free(ctxt);
> >  
> >      return result;
> >  }
> 

[Qemu-devel] [PATCH for-1.2 v3 3/3] check-qjson: add test for large JSON objects

[Michael Roth]

Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
---
 tests/check-qjson.c |   53 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)

diff --git a/tests/check-qjson.c b/tests/check-qjson.c
index 526e25e..3b896f5 100644
--- a/tests/check-qjson.c
+++ b/tests/check-qjson.c
@@ -466,6 +466,58 @@ static void simple_dict(void)
     }
 }
 
+/*
+ * this generates json of the form:
+ * a(0,m) = [0, 1, ..., m-1]
+ * a(n,m) = {
+ *            'key0': a(0,m),
+ *            'key1': a(1,m),
+ *            ...
+ *            'key(n-1)': a(n-1,m)
+ *          }
+ */
+static void gen_test_json(GString *gstr, int nest_level_max,
+                          int elem_count)
+{
+    int i;
+
+    g_assert(gstr);
+    if (nest_level_max == 0) {
+        g_string_append(gstr, "[");
+        for (i = 0; i < elem_count; i++) {
+            g_string_append_printf(gstr, "%d", i);
+            if (i < elem_count - 1) {
+                g_string_append_printf(gstr, ", ");
+            }
+        }
+        g_string_append(gstr, "]");
+        return;
+    }
+
+    g_string_append(gstr, "{");
+    for (i = 0; i < nest_level_max; i++) {
+        g_string_append_printf(gstr, "'key%d': ", i);
+        gen_test_json(gstr, i, elem_count);
+        if (i < nest_level_max - 1) {
+            g_string_append(gstr, ",");
+        }
+    }
+    g_string_append(gstr, "}");
+}
+
+static void large_dict(void)
+{
+    GString *gstr = g_string_new("");
+    QObject *obj;
+
+    gen_test_json(gstr, 10, 100);
+    obj = qobject_from_json(gstr->str);
+    g_assert(obj != NULL);
+
+    qobject_decref(obj);
+    g_string_free(gstr, true);
+}
+
 static void simple_list(void)
 {
     int i;
@@ -706,6 +758,7 @@ int main(int argc, char **argv)
     g_test_add_func("/literals/keyword", keyword_literal);
 
     g_test_add_func("/dicts/simple_dict", simple_dict);
+    g_test_add_func("/dicts/large_dict", large_dict);
     g_test_add_func("/lists/simple_list", simple_list);
 
     g_test_add_func("/whitespace/simple_whitespace", simple_whitespace);
-- 
1.7.9.5

Re: [Qemu-devel] [PATCH for-1.2 v3 1/3] qlist: add qlist_size()

[Eric Blake]

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

On 08/15/2012 12:45 PM, Michael Roth wrote:
> Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
> ---
>  qlist.c |   13 +++++++++++++
>  qlist.h |    1 +
>  2 files changed, 14 insertions(+)

No cover-letter?

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: 620 bytes --]

Re: [Qemu-devel] [PATCH for-1.2 v3 1/3] qlist: add qlist_size()

[Michael Roth]

On Wed, Aug 15, 2012 at 01:52:33PM -0600, Eric Blake wrote:
> On 08/15/2012 12:45 PM, Michael Roth wrote:
> > Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
> > ---
> >  qlist.c |   13 +++++++++++++
> >  qlist.h |    1 +
> >  2 files changed, 14 insertions(+)
> 
> No cover-letter?

Started off as 1 patch with the explanation in the commit

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

Re: [Qemu-devel] [PATCH for-1.2 v3 1/3] qlist: add qlist_size()

[Luiz Capitulino]

On Wed, 15 Aug 2012 13:45:42 -0500
Michael Roth <mdroth@linux.vnet.ibm.com> wrote:

> 
> Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>

I've applied this series to the qmp branch for 1.2. I'll run some tests and if
all goes alright will send a pull request shortly.

> ---
>  qlist.c |   13 +++++++++++++
>  qlist.h |    1 +
>  2 files changed, 14 insertions(+)
> 
> diff --git a/qlist.c b/qlist.c
> index 88498b1..b48ec5b 100644
> --- a/qlist.c
> +++ b/qlist.c
> @@ -124,6 +124,19 @@ int qlist_empty(const QList *qlist)
>      return QTAILQ_EMPTY(&qlist->head);
>  }
>  
> +static void qlist_size_iter(QObject *obj, void *opaque)
> +{
> +    size_t *count = opaque;
> +    (*count)++;
> +}
> +
> +size_t qlist_size(const QList *qlist)
> +{
> +    size_t count = 0;
> +    qlist_iter(qlist, qlist_size_iter, &count);
> +    return count;
> +}
> +
>  /**
>   * qobject_to_qlist(): Convert a QObject into a QList
>   */
> diff --git a/qlist.h b/qlist.h
> index d426bd4..ae776f9 100644
> --- a/qlist.h
> +++ b/qlist.h
> @@ -49,6 +49,7 @@ void qlist_iter(const QList *qlist,
>  QObject *qlist_pop(QList *qlist);
>  QObject *qlist_peek(QList *qlist);
>  int qlist_empty(const QList *qlist);
> +size_t qlist_size(const QList *qlist);
>  QList *qobject_to_qlist(const QObject *obj);
>  
>  static inline const QListEntry *qlist_first(const QList *qlist)

Re: [Qemu-devel] [PATCH for-1.2 v3 1/3] qlist: add qlist_size()

[Michael Roth]

On Thu, Aug 16, 2012 at 10:40:05AM -0300, Luiz Capitulino wrote:
> On Wed, 15 Aug 2012 13:45:42 -0500
> Michael Roth <mdroth@linux.vnet.ibm.com> wrote:
> 
> > 
> > Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
> 
> I've applied this series to the qmp branch for 1.2. I'll run some tests and if
> all goes alright will send a pull request shortly.
> 

I just noticed via our fancy #qemu github bot that Anthony
applied these already, but I asked about and if you want to
test/submit through your queue it should all work out. So either
way.

Thanks!

> > ---
> >  qlist.c |   13 +++++++++++++
> >  qlist.h |    1 +
> >  2 files changed, 14 insertions(+)
> > 
> > diff --git a/qlist.c b/qlist.c
> > index 88498b1..b48ec5b 100644
> > --- a/qlist.c
> > +++ b/qlist.c
> > @@ -124,6 +124,19 @@ int qlist_empty(const QList *qlist)
> >      return QTAILQ_EMPTY(&qlist->head);
> >  }
> >  
> > +static void qlist_size_iter(QObject *obj, void *opaque)
> > +{
> > +    size_t *count = opaque;
> > +    (*count)++;
> > +}
> > +
> > +size_t qlist_size(const QList *qlist)
> > +{
> > +    size_t count = 0;
> > +    qlist_iter(qlist, qlist_size_iter, &count);
> > +    return count;
> > +}
> > +
> >  /**
> >   * qobject_to_qlist(): Convert a QObject into a QList
> >   */
> > diff --git a/qlist.h b/qlist.h
> > index d426bd4..ae776f9 100644
> > --- a/qlist.h
> > +++ b/qlist.h
> > @@ -49,6 +49,7 @@ void qlist_iter(const QList *qlist,
> >  QObject *qlist_pop(QList *qlist);
> >  QObject *qlist_peek(QList *qlist);
> >  int qlist_empty(const QList *qlist);
> > +size_t qlist_size(const QList *qlist);
> >  QList *qobject_to_qlist(const QObject *obj);
> >  
> >  static inline const QListEntry *qlist_first(const QList *qlist)
> 

Re: [Qemu-devel] [PATCH for-1.2 v3 1/3] qlist: add qlist_size()

[Luiz Capitulino]

On Thu, 16 Aug 2012 14:23:40 -0500
Michael Roth <mdroth@linux.vnet.ibm.com> wrote:

> On Thu, Aug 16, 2012 at 10:40:05AM -0300, Luiz Capitulino wrote:
> > On Wed, 15 Aug 2012 13:45:42 -0500
> > Michael Roth <mdroth@linux.vnet.ibm.com> wrote:
> > 
> > > 
> > > Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
> > 
> > I've applied this series to the qmp branch for 1.2. I'll run some tests and if
> > all goes alright will send a pull request shortly.
> > 
> 
> I just noticed via our fancy #qemu github bot that Anthony
> applied these already, but I asked about and if you want to
> test/submit through your queue it should all work out. So either
> way.

I've already tested it, and worked fine here. Let it go through Anthony's
work flow then, saves me a pull request :)