[Qemu-devel] [PATCH] Do not use slow [*] expansion for GPIO creation

[Qemu-devel] [PATCH] Do not use slow [*] expansion for GPIO creation

[Pavel Fedin]

Expansion of [*] suffix is very slow because index expansion is done using
trial and error strategy, starting every time from zero and retrying with
the next index until insertion succeeds. With large number of already added
properties this process takes huge amount of time (O(n^2) complexity).

Some architectures (like ARM) use very large amount of IRQ pins in interrupt
controller models. This flaw makes machine startup extremely slow
(~20 seconds for ARM64 with 32 CPUs. This patch decreases this time down to
~10 seconds.

Signed-off-by: Pavel Fedin <p.fedin@samsung.com>
---
 hw/core/qdev.c | 29 ++++++++++++++++++++++++-----
 1 file changed, 24 insertions(+), 5 deletions(-)

diff --git a/hw/core/qdev.c b/hw/core/qdev.c
index b2f404a..d285784 100644
--- a/hw/core/qdev.c
+++ b/hw/core/qdev.c
@@ -25,6 +25,8 @@
    inherit from a particular bus (e.g. PCI or I2C) rather than
    this API directly.  */
 
+#include <glib/gprintf.h>
+
 #include "hw/qdev.h"
 #include "hw/fw-path-provider.h"
 #include "sysemu/sysemu.h"
@@ -415,15 +417,24 @@ static NamedGPIOList *qdev_get_named_gpio_list(DeviceState *dev,
 void qdev_init_gpio_in_named(DeviceState *dev, qemu_irq_handler handler,
                              const char *name, int n)
 {
-    int i;
+    int i, l;
     NamedGPIOList *gpio_list = qdev_get_named_gpio_list(dev, name);
-    char *propname = g_strdup_printf("%s[*]", name ? name : "unnamed-gpio-in");
+    char *propname;
 
     assert(gpio_list->num_out == 0 || !name);
+
+    if (!name) {
+        name = "unnamed-gpio-in";
+    }
+    l = strlen(name);
+    propname = g_malloc(l + 13); /* 10 characters for UINT_MAX plus "[]" */
+    memcpy(propname, name, l);
+
     gpio_list->in = qemu_extend_irqs(gpio_list->in, gpio_list->num_in, handler,
                                      dev, n);
 
     for (i = gpio_list->num_in; i < gpio_list->num_in + n; i++) {
+        g_sprintf(&propname[l], "[%u]", i);
         object_property_add_child(OBJECT(dev), propname,
                                   OBJECT(gpio_list->in[i]), &error_abort);
     }
@@ -440,14 +451,21 @@ void qdev_init_gpio_in(DeviceState *dev, qemu_irq_handler handler, int n)
 void qdev_init_gpio_out_named(DeviceState *dev, qemu_irq *pins,
                               const char *name, int n)
 {
-    int i;
+    int i, l;
     NamedGPIOList *gpio_list = qdev_get_named_gpio_list(dev, name);
-    char *propname = g_strdup_printf("%s[*]", name ? name : "unnamed-gpio-out");
+    char *propname;
 
     assert(gpio_list->num_in == 0 || !name);
-    gpio_list->num_out += n;
+
+    if (!name) {
+        name = "unnamed-gpio-out";
+    }
+    l = strlen(name);
+    propname = g_malloc(l + 13); /* 10 characters for UINT_MAX plus "[]" */
+    memcpy(propname, name, l);
 
     for (i = 0; i < n; ++i) {
+        g_sprintf(&propname[l], "[%u]", gpio_list->num_out + i);
         memset(&pins[i], 0, sizeof(*pins));
         object_property_add_link(OBJECT(dev), propname, TYPE_IRQ,
                                  (Object **)&pins[i],
@@ -456,6 +474,7 @@ void qdev_init_gpio_out_named(DeviceState *dev, qemu_irq *pins,
                                  &error_abort);
     }
     g_free(propname);
+    gpio_list->num_out += n;
 }
 
 void qdev_init_gpio_out(DeviceState *dev, qemu_irq *pins, int n)
-- 
1.9.5.msysgit.0

Re: [Qemu-devel] [PATCH] Do not use slow [*] expansion for GPIO creation

[Daniel P. Berrange]

On Wed, Jul 29, 2015 at 03:55:14PM +0300, Pavel Fedin wrote:
> Expansion of [*] suffix is very slow because index expansion is done using
> trial and error strategy, starting every time from zero and retrying with
> the next index until insertion succeeds. With large number of already added
> properties this process takes huge amount of time (O(n^2) complexity).
> 
> Some architectures (like ARM) use very large amount of IRQ pins in interrupt
> controller models. This flaw makes machine startup extremely slow
> (~20 seconds for ARM64 with 32 CPUs. This patch decreases this time down to
> ~10 seconds.
> 
> Signed-off-by: Pavel Fedin <p.fedin@samsung.com>
> ---
>  hw/core/qdev.c | 29 ++++++++++++++++++++++++-----
>  1 file changed, 24 insertions(+), 5 deletions(-)
> 
> diff --git a/hw/core/qdev.c b/hw/core/qdev.c
> index b2f404a..d285784 100644
> --- a/hw/core/qdev.c
> +++ b/hw/core/qdev.c
> @@ -25,6 +25,8 @@
>     inherit from a particular bus (e.g. PCI or I2C) rather than
>     this API directly.  */
>  
> +#include <glib/gprintf.h>
> +
>  #include "hw/qdev.h"
>  #include "hw/fw-path-provider.h"
>  #include "sysemu/sysemu.h"
> @@ -415,15 +417,24 @@ static NamedGPIOList *qdev_get_named_gpio_list(DeviceState *dev,
>  void qdev_init_gpio_in_named(DeviceState *dev, qemu_irq_handler handler,
>                               const char *name, int n)
>  {
> -    int i;
> +    int i, l;
>      NamedGPIOList *gpio_list = qdev_get_named_gpio_list(dev, name);
> -    char *propname = g_strdup_printf("%s[*]", name ? name : "unnamed-gpio-in");
> +    char *propname;
>  
>      assert(gpio_list->num_out == 0 || !name);
> +
> +    if (!name) {
> +        name = "unnamed-gpio-in";
> +    }
> +    l = strlen(name);
> +    propname = g_malloc(l + 13); /* 10 characters for UINT_MAX plus "[]" */
> +    memcpy(propname, name, l);

Please don't do manual string length calculations in combination with
unbounded sprintf calls. It is a recipe for future security bugs.

> +
>      gpio_list->in = qemu_extend_irqs(gpio_list->in, gpio_list->num_in, handler,
>                                       dev, n);
>  
>      for (i = gpio_list->num_in; i < gpio_list->num_in + n; i++) {
> +        g_sprintf(&propname[l], "[%u]", i);

Replace this with

    gchar *propname = g_strdup_printf("%s[%u]", name, i)

>          object_property_add_child(OBJECT(dev), propname,
>                                    OBJECT(gpio_list->in[i]), &error_abort);

    g_free(propname);

>      }
> @@ -440,14 +451,21 @@ void qdev_init_gpio_in(DeviceState *dev, qemu_irq_handler handler, int n)
>  void qdev_init_gpio_out_named(DeviceState *dev, qemu_irq *pins,
>                                const char *name, int n)
>  {
> -    int i;
> +    int i, l;
>      NamedGPIOList *gpio_list = qdev_get_named_gpio_list(dev, name);
> -    char *propname = g_strdup_printf("%s[*]", name ? name : "unnamed-gpio-out");
> +    char *propname;
>  
>      assert(gpio_list->num_in == 0 || !name);
> -    gpio_list->num_out += n;
> +
> +    if (!name) {
> +        name = "unnamed-gpio-out";
> +    }
> +    l = strlen(name);
> +    propname = g_malloc(l + 13); /* 10 characters for UINT_MAX plus "[]" */
> +    memcpy(propname, name, l);

Same again here.

>  
>      for (i = 0; i < n; ++i) {
> +        g_sprintf(&propname[l], "[%u]", gpio_list->num_out + i);
>          memset(&pins[i], 0, sizeof(*pins));
>          object_property_add_link(OBJECT(dev), propname, TYPE_IRQ,
>                                   (Object **)&pins[i],
> @@ -456,6 +474,7 @@ void qdev_init_gpio_out_named(DeviceState *dev, qemu_irq *pins,
>                                   &error_abort);
>      }
>      g_free(propname);
> +    gpio_list->num_out += n;
>  }

Regards,
Daniel
-- 
|: http://berrange.com      -o-    http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org              -o-             http://virt-manager.org :|
|: http://autobuild.org       -o-         http://search.cpan.org/~danberr/ :|
|: http://entangle-photo.org       -o-       http://live.gnome.org/gtk-vnc :|

Re: [Qemu-devel] [PATCH] Do not use slow [*] expansion for GPIO creation

[Pavel Fedin]

 Hello!

> > +    l = strlen(name);
> > +    propname = g_malloc(l + 13); /* 10 characters for UINT_MAX plus "[]" */
> > +    memcpy(propname, name, l);
> 
> Please don't do manual string length calculations in combination with
> unbounded sprintf calls. It is a recipe for future security bugs.

[skip]

> >      for (i = gpio_list->num_in; i < gpio_list->num_in + n; i++) {
> > +        g_sprintf(&propname[l], "[%u]", i);
> 
> Replace this with
> 
>     gchar *propname = g_strdup_printf("%s[%u]", name, i)
> 
> >          object_property_add_child(OBJECT(dev), propname,
> >                                    OBJECT(gpio_list->in[i]), &error_abort);
> 
>     g_free(propname);

 IMHO it's not really good because of repeating allocation-free. This is not VERY slow, but still slower than it could be (imagine that this repeats ~1000 times).
 I have a better idea instead. What if instead:

propname = g_malloc(l + 13); /* 10 characters for UINT_MAX plus "[]" */

 i do:

propname = g_strdup_printf("%s[%u]", name, -1)

 ? This will automatically give me a buffer to fit in the largest possible integer.

Kind regards,
Pavel Fedin
Expert Engineer
Samsung Electronics Research center Russia

Re: [Qemu-devel] [PATCH] Do not use slow [*] expansion for GPIO creation

[Daniel P. Berrange]

On Wed, Jul 29, 2015 at 05:08:18PM +0300, Pavel Fedin wrote:
>  Hello!
> 
> > > +    l = strlen(name);
> > > +    propname = g_malloc(l + 13); /* 10 characters for UINT_MAX plus "[]" */
> > > +    memcpy(propname, name, l);
> > 
> > Please don't do manual string length calculations in combination with
> > unbounded sprintf calls. It is a recipe for future security bugs.
> 
> [skip]
> 
> > >      for (i = gpio_list->num_in; i < gpio_list->num_in + n; i++) {
> > > +        g_sprintf(&propname[l], "[%u]", i);
> > 
> > Replace this with
> > 
> >     gchar *propname = g_strdup_printf("%s[%u]", name, i)
> > 
> > >          object_property_add_child(OBJECT(dev), propname,
> > >                                    OBJECT(gpio_list->in[i]), &error_abort);
> > 
> >     g_free(propname);
> 
>  IMHO it's not really good because of repeating allocation-free. This
>  is not VERY slow, but still slower than it could be (imagine that this
>  repeats ~1000 times).

Unless this repeated allocation overhead is illustrated to be a real world
problem, I think using g_strdup_printf is preferrable.

>  I have a better idea instead. What if instead:
> 
> propname = g_malloc(l + 13); /* 10 characters for UINT_MAX plus "[]" */
> 
>  i do:
> 
> propname = g_strdup_printf("%s[%u]", name, -1)
> 
>  ? This will automatically give me a buffer to fit in the largest possible integer.

I think it is premature/unneccesary optimization unless there are bench
marks to show this is a real world problem.

Regards,
Daniel
-- 
|: http://berrange.com      -o-    http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org              -o-             http://virt-manager.org :|
|: http://autobuild.org       -o-         http://search.cpan.org/~danberr/ :|
|: http://entangle-photo.org       -o-       http://live.gnome.org/gtk-vnc :|