Re: [Qemu-devel] [PATCH] qapi: change QmpInputVisitor to QSLIST

[Markus Armbruster <armbru@redhat.com>]

Needs a rebase.  The other one, too.

Paolo Bonzini <pbonzini@redhat.com> writes:

> This saves a lot of memory compared to a statically-sized array.
>
> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>

Saves 24KiB - d*32B.  That's "a lot" for an Atari ST or something, or if
you're juggling hundreds of these things at the same time.

Allocating 24KiB and using only the first d*24 bytes is simpler and
generally faster than allocating d chunks of 32B each.  But I won't
argue, as I'm pretty confident that neither memory nor CPU use of this
code matter.

Another reason not to argue: commit e38ac96 already added a per-depth
allocation.

So all I ask for here is s/a lot of memory/some memory/.

The patch makes QmpInputVisitor more similar to QmpOutputVisitor, which
is nice.

> ---
>  qapi/qmp-input-visitor.c | 53 ++++++++++++++++++++++++------------------------
>  1 file changed, 26 insertions(+), 27 deletions(-)
>
> diff --git a/qapi/qmp-input-visitor.c b/qapi/qmp-input-visitor.c
> index aea90a1..28629b1 100644
> --- a/qapi/qmp-input-visitor.c
> +++ b/qapi/qmp-input-visitor.c
> @@ -29,6 +29,8 @@ typedef struct StackObject
>  
>      GHashTable *h;           /* If obj is dict: unvisited keys */
>      const QListEntry *entry; /* If obj is list: unvisited tail */
> +
> +    QSLIST_ENTRY(StackObject) node;
>  } StackObject;
>  
>  struct QmpInputVisitor
> @@ -40,8 +42,7 @@ struct QmpInputVisitor
>  
>      /* Stack of objects being visited (all entries will be either
>       * QDict or QList). */
> -    StackObject stack[QIV_STACK_SIZE];
> -    int nb_stack;
> +    QSLIST_HEAD(, StackObject) stack;
>  
>      /* True to reject parse in visit_end_struct() if unvisited keys remain. */
>      bool strict;
> @@ -60,13 +61,13 @@ static QObject *qmp_input_get_object(QmpInputVisitor *qiv,
>      QObject *qobj;
>      QObject *ret;
>  
> -    if (!qiv->nb_stack) {
> +    if (QSLIST_EMPTY(&qiv->stack)) {
>          /* Starting at root, name is ignored. */
>          return qiv->root;
>      }
>  
>      /* We are in a container; find the next element. */
> -    tos = &qiv->stack[qiv->nb_stack - 1];
> +    tos = QSLIST_FIRST(&qiv->stack);
>      qobj = tos->obj;
>      assert(qobj);
>  
> @@ -99,17 +100,10 @@ static const QListEntry *qmp_input_push(QmpInputVisitor *qiv, QObject *obj,
>                                          Error **errp)
>  {
>      GHashTable *h;
> -    StackObject *tos = &qiv->stack[qiv->nb_stack];
> +    StackObject *tos = g_new0(StackObject, 1);
>  
>      assert(obj);
> -    if (qiv->nb_stack >= QIV_STACK_SIZE) {
> -        error_setg(errp, "An internal buffer overran");
> -        return NULL;
> -    }

Removing the arbitrary limit is aesthetically pleasing.  But can
untrusted input make us allocate unbounded amounts of memory now?

> -
>      tos->obj = obj;
> -    assert(!tos->h);
> -    assert(!tos->entry);

Why do you delete these two?

>  
>      if (qiv->strict && qobject_type(obj) == QTYPE_QDICT) {
>          h = g_hash_table_new(g_str_hash, g_str_equal);
> @@ -119,7 +113,7 @@ static const QListEntry *qmp_input_push(QmpInputVisitor *qiv, QObject *obj,
>          tos->entry = qlist_first(qobject_to_qlist(obj));
>      }
>  
> -    qiv->nb_stack++;
> +    QSLIST_INSERT_HEAD(&qiv->stack, tos, node);
>      return tos->entry;
>  }
>  
> @@ -127,9 +121,7 @@ static const QListEntry *qmp_input_push(QmpInputVisitor *qiv, QObject *obj,
>  static void qmp_input_check_struct(Visitor *v, Error **errp)
>  {
>      QmpInputVisitor *qiv = to_qiv(v);
> -    StackObject *tos = &qiv->stack[qiv->nb_stack - 1];
> -
> -    assert(qiv->nb_stack > 0);
> +    StackObject *tos = QSLIST_FIRST(&qiv->stack);

As Eric noted, we could assert(tos) here.  Not sure I'd bother, because
we dereference it unless !qiv->strict.

>  
>      if (qiv->strict) {
>          GHashTable *const top_ht = tos->h;
> @@ -145,22 +137,25 @@ static void qmp_input_check_struct(Visitor *v, Error **errp)
>      }
>  }
>  
> -static void qmp_input_pop(Visitor *v)
> +static void qmp_input_stack_pop(QmpInputVisitor *qiv)
>  {
> -    QmpInputVisitor *qiv = to_qiv(v);
> -    StackObject *tos = &qiv->stack[qiv->nb_stack - 1];
> -
> -    assert(qiv->nb_stack > 0);
> +    StackObject *tos = QSLIST_FIRST(&qiv->stack);

Likewise, except latest upstream already has assert(tos->qapi == obj)
here, and sticking in tos && is cheap.

>  
>      if (qiv->strict) {
> -        GHashTable * const top_ht = qiv->stack[qiv->nb_stack - 1].h;
> -        if (top_ht) {
> -            g_hash_table_unref(top_ht);
> +        if (tos->h) {
> +            g_hash_table_unref(tos->h);
>          }
> -        tos->h = NULL;
>      }
>  
> -    qiv->nb_stack--;
> +    QSLIST_REMOVE_HEAD(&qiv->stack, node);
> +    g_free(tos);
> +}
> +
> +static void qmp_input_pop(Visitor *v)
> +{
> +    QmpInputVisitor *qiv = to_qiv(v);
> +
> +    qmp_input_stack_pop(qiv);
>  }
>  
>  static void qmp_input_start_struct(Visitor *v, const char *name, void **obj,
> @@ -221,7 +216,7 @@ static GenericList *qmp_input_next_list(Visitor *v, GenericList *tail,
>                                          size_t size)
>  {
>      QmpInputVisitor *qiv = to_qiv(v);
> -    StackObject *so = &qiv->stack[qiv->nb_stack - 1];
> +    StackObject *so = QSLIST_FIRST(&qiv->stack);
>  
>      if (!so->entry) {
>          return NULL;
> @@ -377,6 +372,10 @@ Visitor *qmp_input_get_visitor(QmpInputVisitor *v)
>  
>  void qmp_input_visitor_cleanup(QmpInputVisitor *v)
>  {
> +    while (!QSLIST_EMPTY(&v->stack)) {
> +        qmp_input_stack_pop(v);
> +    }
> +
>      qobject_decref(v->root);
>      g_free(v);
>  }