qemu-devel.nongnu.org archive mirror
 help / color / mirror / Atom feed
* [Qemu-devel] [PATCH 1/2] Add interface to traverse the qmp command list by QmpCommand
@ 2013-10-09  2:36 Mark Wu
  2013-10-09  2:42 ` Mark Wu
  0 siblings, 1 reply; 2+ messages in thread
From: Mark Wu @ 2013-10-09  2:36 UTC (permalink / raw)
  To: Qemu-devel; +Cc: Mark Wu, Michael Roth, Luiz Capitulino

In the original code, qmp_get_command_list is used to construct
a list of all commands' name. To get the information of all qga
commands, it traverses the name list and search the command info
with its name.  So it can cause O(n^2) in the number of commands.

This patch adds an interface to traverse the qmp command list by
QmpCommand to replace qmp_get_command_list. It can decrease the
complexity from O(n^2) to O(n).

Signed-off-by: Mark Wu <wudxw@linux.vnet.ibm.com>
---
v3:
    Add an accessor for cmd->name to avoid exposing internals of QmpCommand
v2:
	1. Keep the signature of qmp_command_is_enabled (per Eric and Michael)
    2. Remove the unnecessary pointer castings (per Eric)

 include/qapi/qmp/dispatch.h |  6 ++--
 qapi/qmp-registry.c         | 30 +++++-------------
 qga/commands.c              | 38 +++++++++--------------
 qga/main.c                  | 75 ++++++++++++++++++---------------------------
 4 files changed, 57 insertions(+), 92 deletions(-)

diff --git a/include/qapi/qmp/dispatch.h b/include/qapi/qmp/dispatch.h
index 1ce11f5..7d759ef 100644
--- a/include/qapi/qmp/dispatch.h
+++ b/include/qapi/qmp/dispatch.h
@@ -47,9 +47,11 @@ QmpCommand *qmp_find_command(const char *name);
 QObject *qmp_dispatch(QObject *request);
 void qmp_disable_command(const char *name);
 void qmp_enable_command(const char *name);
-bool qmp_command_is_enabled(const char *name);
-char **qmp_get_command_list(void);
+bool qmp_command_is_enabled(const QmpCommand *cmd);
+const char *qmp_command_name(const QmpCommand *cmd);
 QObject *qmp_build_error_object(Error *errp);
+typedef void (*qmp_cmd_callback_fn)(QmpCommand *cmd, void *opaque);
+void qmp_for_each_command(qmp_cmd_callback_fn fn, void *opaque);
 
 #endif
 
diff --git a/qapi/qmp-registry.c b/qapi/qmp-registry.c
index 28bbbe8..5e26710 100644
--- a/qapi/qmp-registry.c
+++ b/qapi/qmp-registry.c
@@ -66,35 +66,21 @@ void qmp_enable_command(const char *name)
     qmp_toggle_command(name, true);
 }
 
-bool qmp_command_is_enabled(const char *name)
+bool qmp_command_is_enabled(const QmpCommand *cmd)
 {
-    QmpCommand *cmd;
-
-    QTAILQ_FOREACH(cmd, &qmp_commands, node) {
-        if (strcmp(cmd->name, name) == 0) {
-            return cmd->enabled;
-        }
-    }
+    return cmd->enabled;
+}
 
-    return false;
+const char *qmp_command_name(const QmpCommand *cmd)
+{
+    return cmd->name;
 }
 
-char **qmp_get_command_list(void)
+void qmp_for_each_command(qmp_cmd_callback_fn fn, void *opaque)
 {
     QmpCommand *cmd;
-    int count = 1;
-    char **list_head, **list;
-
-    QTAILQ_FOREACH(cmd, &qmp_commands, node) {
-        count++;
-    }
-
-    list_head = list = g_malloc0(count * sizeof(char *));
 
     QTAILQ_FOREACH(cmd, &qmp_commands, node) {
-        *list = g_strdup(cmd->name);
-        list++;
+        fn(cmd, opaque);
     }
-
-    return list_head;
 }
diff --git a/qga/commands.c b/qga/commands.c
index 528b082..063b22b 100644
--- a/qga/commands.c
+++ b/qga/commands.c
@@ -45,35 +45,27 @@ void qmp_guest_ping(Error **err)
     slog("guest-ping called");
 }
 
-struct GuestAgentInfo *qmp_guest_info(Error **err)
+static void qmp_command_info(QmpCommand *cmd, void *opaque)
 {
-    GuestAgentInfo *info = g_malloc0(sizeof(GuestAgentInfo));
+    GuestAgentInfo *info = opaque;
     GuestAgentCommandInfo *cmd_info;
     GuestAgentCommandInfoList *cmd_info_list;
-    char **cmd_list_head, **cmd_list;
-
-    info->version = g_strdup(QEMU_VERSION);
-
-    cmd_list_head = cmd_list = qmp_get_command_list();
-    if (*cmd_list_head == NULL) {
-        goto out;
-    }
 
-    while (*cmd_list) {
-        cmd_info = g_malloc0(sizeof(GuestAgentCommandInfo));
-        cmd_info->name = g_strdup(*cmd_list);
-        cmd_info->enabled = qmp_command_is_enabled(cmd_info->name);
+    cmd_info = g_malloc0(sizeof(GuestAgentCommandInfo));
+    cmd_info->name = g_strdup(cmd->name);
+    cmd_info->enabled = qmp_command_is_enabled(cmd);
 
-        cmd_info_list = g_malloc0(sizeof(GuestAgentCommandInfoList));
-        cmd_info_list->value = cmd_info;
-        cmd_info_list->next = info->supported_commands;
-        info->supported_commands = cmd_info_list;
+    cmd_info_list = g_malloc0(sizeof(GuestAgentCommandInfoList));
+    cmd_info_list->value = cmd_info;
+    cmd_info_list->next = info->supported_commands;
+    info->supported_commands = cmd_info_list;
+}
 
-        g_free(*cmd_list);
-        cmd_list++;
-    }
+struct GuestAgentInfo *qmp_guest_info(Error **err)
+{
+    GuestAgentInfo *info = g_malloc0(sizeof(GuestAgentInfo));
 
-out:
-    g_free(cmd_list_head);
+    info->version = g_strdup(QEMU_VERSION);
+    qmp_for_each_command(qmp_command_info, info);
     return info;
 }
diff --git a/qga/main.c b/qga/main.c
index 6c746c8..c58b26a 100644
--- a/qga/main.c
+++ b/qga/main.c
@@ -347,48 +347,35 @@ static gint ga_strcmp(gconstpointer str1, gconstpointer str2)
 }
 
 /* disable commands that aren't safe for fsfreeze */
-static void ga_disable_non_whitelisted(void)
+static void ga_disable_non_whitelisted(QmpCommand *cmd, void *opaque)
 {
-    char **list_head, **list;
-    bool whitelisted;
-    int i;
-
-    list_head = list = qmp_get_command_list();
-    while (*list != NULL) {
-        whitelisted = false;
-        i = 0;
-        while (ga_freeze_whitelist[i] != NULL) {
-            if (strcmp(*list, ga_freeze_whitelist[i]) == 0) {
-                whitelisted = true;
-            }
-            i++;
-        }
-        if (!whitelisted) {
-            g_debug("disabling command: %s", *list);
-            qmp_disable_command(*list);
+    bool whitelisted = false;
+    int i = 0;
+    const char *name = qmp_command_name(cmd);
+
+    while (ga_freeze_whitelist[i] != NULL) {
+        if (strcmp(name, ga_freeze_whitelist[i]) == 0) {
+            whitelisted = true;
         }
-        g_free(*list);
-        list++;
+        i++;
+    }
+    if (!whitelisted) {
+        g_debug("disabling command: %s", name);
+        qmp_disable_command(name);
     }
-    g_free(list_head);
 }
 
 /* [re-]enable all commands, except those explicitly blacklisted by user */
-static void ga_enable_non_blacklisted(GList *blacklist)
+static void ga_enable_non_blacklisted(QmpCommand *cmd, void *opaque)
 {
-    char **list_head, **list;
-
-    list_head = list = qmp_get_command_list();
-    while (*list != NULL) {
-        if (g_list_find_custom(blacklist, *list, ga_strcmp) == NULL &&
-            !qmp_command_is_enabled(*list)) {
-            g_debug("enabling command: %s", *list);
-            qmp_enable_command(*list);
-        }
-        g_free(*list);
-        list++;
+    GList *blacklist = opaque;
+    const char *name = qmp_command_name(cmd);
+
+    if (g_list_find_custom(blacklist, name, ga_strcmp) == NULL &&
+        !qmp_command_is_enabled(cmd)) {
+        g_debug("enabling command: %s", name);
+        qmp_enable_command(name);
     }
-    g_free(list_head);
 }
 
 static bool ga_create_file(const char *path)
@@ -424,7 +411,7 @@ void ga_set_frozen(GAState *s)
         return;
     }
     /* disable all non-whitelisted (for frozen state) commands */
-    ga_disable_non_whitelisted();
+    qmp_for_each_command(ga_disable_non_whitelisted, NULL);
     g_warning("disabling logging due to filesystem freeze");
     ga_disable_logging(s);
     s->frozen = true;
@@ -460,7 +447,7 @@ void ga_unset_frozen(GAState *s)
     }
 
     /* enable all disabled, non-blacklisted commands */
-    ga_enable_non_blacklisted(s->blacklist);
+    qmp_for_each_command(ga_enable_non_blacklisted, s->blacklist);
     s->frozen = false;
     if (!ga_delete_file(s->state_filepath_isfrozen)) {
         g_warning("unable to delete %s, fsfreeze may not function properly",
@@ -920,6 +907,11 @@ int64_t ga_get_fd_handle(GAState *s, Error **errp)
     return handle;
 }
 
+static void ga_print_cmd(QmpCommand *cmd, void *opaque)
+{
+    printf("%s\n", qmp_command_name(cmd));
+}
+
 int main(int argc, char **argv)
 {
     const char *sopt = "hVvdm:p:l:f:F::b:s:t:";
@@ -996,15 +988,8 @@ int main(int argc, char **argv)
             daemonize = 1;
             break;
         case 'b': {
-            char **list_head, **list;
             if (is_help_option(optarg)) {
-                list_head = list = qmp_get_command_list();
-                while (*list != NULL) {
-                    printf("%s\n", *list);
-                    g_free(*list);
-                    list++;
-                }
-                g_free(list_head);
+                qmp_for_each_command(ga_print_cmd, NULL);
                 return 0;
             }
             for (j = 0, i = 0, len = strlen(optarg); i < len; i++) {
@@ -1126,7 +1111,7 @@ int main(int argc, char **argv)
             s->deferred_options.log_filepath = log_filepath;
         }
         ga_disable_logging(s);
-        ga_disable_non_whitelisted();
+        qmp_for_each_command(ga_disable_non_whitelisted, NULL);
     } else {
         if (daemonize) {
             become_daemon(pid_filepath);
-- 
1.8.3.1

^ permalink raw reply related	[flat|nested] 2+ messages in thread

* Re: [Qemu-devel] [PATCH 1/2] Add interface to traverse the qmp command list by QmpCommand
  2013-10-09  2:36 [Qemu-devel] [PATCH 1/2] Add interface to traverse the qmp command list by QmpCommand Mark Wu
@ 2013-10-09  2:42 ` Mark Wu
  0 siblings, 0 replies; 2+ messages in thread
From: Mark Wu @ 2013-10-09  2:42 UTC (permalink / raw)
  To: Mark Wu; +Cc: qemu-devel, Michael Roth, Luiz Capitulino

On Wed 09 Oct 2013 10:36:21 AM CST, Mark Wu wrote:
> In the original code, qmp_get_command_list is used to construct
> a list of all commands' name. To get the information of all qga
> commands, it traverses the name list and search the command info
> with its name.  So it can cause O(n^2) in the number of commands.
>
> This patch adds an interface to traverse the qmp command list by
> QmpCommand to replace qmp_get_command_list. It can decrease the
> complexity from O(n^2) to O(n).
>
> Signed-off-by: Mark Wu <wudxw@linux.vnet.ibm.com>
> ---
> v3:
>      Add an accessor for cmd->name to avoid exposing internals of QmpCommand
> v2:
> 	1. Keep the signature of qmp_command_is_enabled (per Eric and Michael)
>      2. Remove the unnecessary pointer castings (per Eric)
>
>   include/qapi/qmp/dispatch.h |  6 ++--
>   qapi/qmp-registry.c         | 30 +++++-------------
>   qga/commands.c              | 38 +++++++++--------------
>   qga/main.c                  | 75 ++++++++++++++++++---------------------------
>   4 files changed, 57 insertions(+), 92 deletions(-)
>
> diff --git a/include/qapi/qmp/dispatch.h b/include/qapi/qmp/dispatch.h
> index 1ce11f5..7d759ef 100644
> --- a/include/qapi/qmp/dispatch.h
> +++ b/include/qapi/qmp/dispatch.h
> @@ -47,9 +47,11 @@ QmpCommand *qmp_find_command(const char *name);
>   QObject *qmp_dispatch(QObject *request);
>   void qmp_disable_command(const char *name);
>   void qmp_enable_command(const char *name);
> -bool qmp_command_is_enabled(const char *name);
> -char **qmp_get_command_list(void);
> +bool qmp_command_is_enabled(const QmpCommand *cmd);
> +const char *qmp_command_name(const QmpCommand *cmd);
>   QObject *qmp_build_error_object(Error *errp);
> +typedef void (*qmp_cmd_callback_fn)(QmpCommand *cmd, void *opaque);
> +void qmp_for_each_command(qmp_cmd_callback_fn fn, void *opaque);
>
>   #endif
>
> diff --git a/qapi/qmp-registry.c b/qapi/qmp-registry.c
> index 28bbbe8..5e26710 100644
> --- a/qapi/qmp-registry.c
> +++ b/qapi/qmp-registry.c
> @@ -66,35 +66,21 @@ void qmp_enable_command(const char *name)
>       qmp_toggle_command(name, true);
>   }
>
> -bool qmp_command_is_enabled(const char *name)
> +bool qmp_command_is_enabled(const QmpCommand *cmd)
>   {
> -    QmpCommand *cmd;
> -
> -    QTAILQ_FOREACH(cmd, &qmp_commands, node) {
> -        if (strcmp(cmd->name, name) == 0) {
> -            return cmd->enabled;
> -        }
> -    }
> +    return cmd->enabled;
> +}
>
> -    return false;
> +const char *qmp_command_name(const QmpCommand *cmd)
> +{
> +    return cmd->name;
>   }
>
> -char **qmp_get_command_list(void)
> +void qmp_for_each_command(qmp_cmd_callback_fn fn, void *opaque)
>   {
>       QmpCommand *cmd;
> -    int count = 1;
> -    char **list_head, **list;
> -
> -    QTAILQ_FOREACH(cmd, &qmp_commands, node) {
> -        count++;
> -    }
> -
> -    list_head = list = g_malloc0(count * sizeof(char *));
>
>       QTAILQ_FOREACH(cmd, &qmp_commands, node) {
> -        *list = g_strdup(cmd->name);
> -        list++;
> +        fn(cmd, opaque);
>       }
> -
> -    return list_head;
>   }
> diff --git a/qga/commands.c b/qga/commands.c
> index 528b082..063b22b 100644
> --- a/qga/commands.c
> +++ b/qga/commands.c
> @@ -45,35 +45,27 @@ void qmp_guest_ping(Error **err)
>       slog("guest-ping called");
>   }
>
> -struct GuestAgentInfo *qmp_guest_info(Error **err)
> +static void qmp_command_info(QmpCommand *cmd, void *opaque)
>   {
> -    GuestAgentInfo *info = g_malloc0(sizeof(GuestAgentInfo));
> +    GuestAgentInfo *info = opaque;
>       GuestAgentCommandInfo *cmd_info;
>       GuestAgentCommandInfoList *cmd_info_list;
> -    char **cmd_list_head, **cmd_list;
> -
> -    info->version = g_strdup(QEMU_VERSION);
> -
> -    cmd_list_head = cmd_list = qmp_get_command_list();
> -    if (*cmd_list_head == NULL) {
> -        goto out;
> -    }
>
> -    while (*cmd_list) {
> -        cmd_info = g_malloc0(sizeof(GuestAgentCommandInfo));
> -        cmd_info->name = g_strdup(*cmd_list);
> -        cmd_info->enabled = qmp_command_is_enabled(cmd_info->name);
> +    cmd_info = g_malloc0(sizeof(GuestAgentCommandInfo));
> +    cmd_info->name = g_strdup(cmd->name);
> +    cmd_info->enabled = qmp_command_is_enabled(cmd);
>
> -        cmd_info_list = g_malloc0(sizeof(GuestAgentCommandInfoList));
> -        cmd_info_list->value = cmd_info;
> -        cmd_info_list->next = info->supported_commands;
> -        info->supported_commands = cmd_info_list;
> +    cmd_info_list = g_malloc0(sizeof(GuestAgentCommandInfoList));
> +    cmd_info_list->value = cmd_info;
> +    cmd_info_list->next = info->supported_commands;
> +    info->supported_commands = cmd_info_list;
> +}
>
> -        g_free(*cmd_list);
> -        cmd_list++;
> -    }
> +struct GuestAgentInfo *qmp_guest_info(Error **err)
> +{
> +    GuestAgentInfo *info = g_malloc0(sizeof(GuestAgentInfo));
>
> -out:
> -    g_free(cmd_list_head);
> +    info->version = g_strdup(QEMU_VERSION);
> +    qmp_for_each_command(qmp_command_info, info);
>       return info;
>   }
> diff --git a/qga/main.c b/qga/main.c
> index 6c746c8..c58b26a 100644
> --- a/qga/main.c
> +++ b/qga/main.c
> @@ -347,48 +347,35 @@ static gint ga_strcmp(gconstpointer str1, gconstpointer str2)
>   }
>
>   /* disable commands that aren't safe for fsfreeze */
> -static void ga_disable_non_whitelisted(void)
> +static void ga_disable_non_whitelisted(QmpCommand *cmd, void *opaque)
>   {
> -    char **list_head, **list;
> -    bool whitelisted;
> -    int i;
> -
> -    list_head = list = qmp_get_command_list();
> -    while (*list != NULL) {
> -        whitelisted = false;
> -        i = 0;
> -        while (ga_freeze_whitelist[i] != NULL) {
> -            if (strcmp(*list, ga_freeze_whitelist[i]) == 0) {
> -                whitelisted = true;
> -            }
> -            i++;
> -        }
> -        if (!whitelisted) {
> -            g_debug("disabling command: %s", *list);
> -            qmp_disable_command(*list);
> +    bool whitelisted = false;
> +    int i = 0;
> +    const char *name = qmp_command_name(cmd);
> +
> +    while (ga_freeze_whitelist[i] != NULL) {
> +        if (strcmp(name, ga_freeze_whitelist[i]) == 0) {
> +            whitelisted = true;
>           }
> -        g_free(*list);
> -        list++;
> +        i++;
> +    }
> +    if (!whitelisted) {
> +        g_debug("disabling command: %s", name);
> +        qmp_disable_command(name);
>       }
> -    g_free(list_head);
>   }
>
>   /* [re-]enable all commands, except those explicitly blacklisted by user */
> -static void ga_enable_non_blacklisted(GList *blacklist)
> +static void ga_enable_non_blacklisted(QmpCommand *cmd, void *opaque)
>   {
> -    char **list_head, **list;
> -
> -    list_head = list = qmp_get_command_list();
> -    while (*list != NULL) {
> -        if (g_list_find_custom(blacklist, *list, ga_strcmp) == NULL &&
> -            !qmp_command_is_enabled(*list)) {
> -            g_debug("enabling command: %s", *list);
> -            qmp_enable_command(*list);
> -        }
> -        g_free(*list);
> -        list++;
> +    GList *blacklist = opaque;
> +    const char *name = qmp_command_name(cmd);
> +
> +    if (g_list_find_custom(blacklist, name, ga_strcmp) == NULL &&
> +        !qmp_command_is_enabled(cmd)) {
> +        g_debug("enabling command: %s", name);
> +        qmp_enable_command(name);
>       }
> -    g_free(list_head);
>   }
>
>   static bool ga_create_file(const char *path)
> @@ -424,7 +411,7 @@ void ga_set_frozen(GAState *s)
>           return;
>       }
>       /* disable all non-whitelisted (for frozen state) commands */
> -    ga_disable_non_whitelisted();
> +    qmp_for_each_command(ga_disable_non_whitelisted, NULL);
>       g_warning("disabling logging due to filesystem freeze");
>       ga_disable_logging(s);
>       s->frozen = true;
> @@ -460,7 +447,7 @@ void ga_unset_frozen(GAState *s)
>       }
>
>       /* enable all disabled, non-blacklisted commands */
> -    ga_enable_non_blacklisted(s->blacklist);
> +    qmp_for_each_command(ga_enable_non_blacklisted, s->blacklist);
>       s->frozen = false;
>       if (!ga_delete_file(s->state_filepath_isfrozen)) {
>           g_warning("unable to delete %s, fsfreeze may not function properly",
> @@ -920,6 +907,11 @@ int64_t ga_get_fd_handle(GAState *s, Error **errp)
>       return handle;
>   }
>
> +static void ga_print_cmd(QmpCommand *cmd, void *opaque)
> +{
> +    printf("%s\n", qmp_command_name(cmd));
> +}
> +
>   int main(int argc, char **argv)
>   {
>       const char *sopt = "hVvdm:p:l:f:F::b:s:t:";
> @@ -996,15 +988,8 @@ int main(int argc, char **argv)
>               daemonize = 1;
>               break;
>           case 'b': {
> -            char **list_head, **list;
>               if (is_help_option(optarg)) {
> -                list_head = list = qmp_get_command_list();
> -                while (*list != NULL) {
> -                    printf("%s\n", *list);
> -                    g_free(*list);
> -                    list++;
> -                }
> -                g_free(list_head);
> +                qmp_for_each_command(ga_print_cmd, NULL);
>                   return 0;
>               }
>               for (j = 0, i = 0, len = strlen(optarg); i < len; i++) {
> @@ -1126,7 +1111,7 @@ int main(int argc, char **argv)
>               s->deferred_options.log_filepath = log_filepath;
>           }
>           ga_disable_logging(s);
> -        ga_disable_non_whitelisted();
> +        qmp_for_each_command(ga_disable_non_whitelisted, NULL);
>       } else {
>           if (daemonize) {
>               become_daemon(pid_filepath);

Please ignore this mail because of the wrong patch revision number.  
Sorry for that.

^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2013-10-09  2:42 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2013-10-09  2:36 [Qemu-devel] [PATCH 1/2] Add interface to traverse the qmp command list by QmpCommand Mark Wu
2013-10-09  2:42 ` Mark Wu

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).