[PATCH 08/40] qemu: namespace: Don't use 'virStringListAdd' inside loops

[Michal Privoznik]

On 2/6/21 9:32 AM, Peter Krempa wrote:
> 'virStringListAdd' calculates the string list length on every invocation
> so constructing a string list using it results in O(n^2) complexity.
> 
> Use a GSList which has cheap insertion and iteration and doesn't need
> failure handling.
> 
> Signed-off-by: Peter Krempa <pkrempa at redhat.com>
> ---
>   src/qemu/qemu_namespace.c | 202 ++++++++++++++++++--------------------
>   1 file changed, 98 insertions(+), 104 deletions(-)
> 
> diff --git a/src/qemu/qemu_namespace.c b/src/qemu/qemu_namespace.c
> index af08b3e055..e8f205cfdd 100644
> --- a/src/qemu/qemu_namespace.c
> +++ b/src/qemu/qemu_namespace.c
> @@ -40,6 +40,7 @@
>   #include "virlog.h"
>   #include "virstring.h"
>   #include "virdevmapper.h"
> +#include "virglibutil.h"
> 
>   #define VIR_FROM_THIS VIR_FROM_QEMU
> 
> @@ -190,7 +191,7 @@ qemuDomainGetPreservedMounts(virQEMUDriverConfigPtr cfg,
> 
>   static int
>   qemuDomainPopulateDevices(virQEMUDriverConfigPtr cfg,
> -                          char ***paths)
> +                          GSList **paths)
>   {
>       const char *const *devices = (const char *const *) cfg->cgroupDeviceACL;
>       size_t i;
> @@ -199,8 +200,7 @@ qemuDomainPopulateDevices(virQEMUDriverConfigPtr cfg,
>           devices = defaultDeviceACL;
> 
>       for (i = 0; devices[i]; i++) {
> -        if (virStringListAdd(paths, devices[i]) < 0)
> -            return -1;
> +        *paths = g_slist_prepend(*paths, g_strdup(devices[i]));
>       }
> 
>       return 0;
> @@ -237,7 +237,7 @@ qemuDomainSetupDev(virSecurityManagerPtr mgr,
> 
>   static int
>   qemuDomainSetupDisk(virStorageSourcePtr src,
> -                    char ***paths)
> +                    GSList **paths)
>   {
>       virStorageSourcePtr next;
>       bool hasNVMe = false;
> @@ -252,6 +252,7 @@ qemuDomainSetupDisk(virStorageSourcePtr src,
>                   return -1;
>           } else {
>               g_auto(GStrv) targetPaths = NULL;
> +            GStrv tmp;
> 
>               if (virStorageSourceIsEmpty(next) ||
>                   !virStorageSourceIsLocalStorage(next)) {
> @@ -269,22 +270,19 @@ qemuDomainSetupDisk(virStorageSourcePtr src,
>                   return -1;
>               }
> 
> -            if (virStringListMerge(paths, &targetPaths) < 0)
> -                return -1;
> +            for (tmp = targetPaths; *tmp; tmp++)
> +                *paths = g_slist_prepend(*paths, g_steal_pointer(tmp));

It's not that simple. virStringListMerge() turned into NOP when 
@targetPaths was NULL (which is very easy to achive - just start a 
domain with a disk that's not a devmapper device). This code 
dereferences NULL directly. I think this is the only place that suffers 
from this so you can get away with if (targetPaths) check. Other places 
will demonstrate themselves :-)

Michal