[PATCH v2 03/11] bdrv_change_aio_context: use hash table instead of list of visited nodes

[Emanuele Giuseppe Esposito <eesposit@redhat.com>]

Minor performance improvement, but given that we have hash tables
available, avoid iterating in the visited nodes list every time just
to check if a node has been already visited.

The data structure is not actually a proper hash map, but an hash set,
as we are just adding nodes and not key,value pairs.

Suggested-by: Hanna Reitz <hreitz@redhat.com>
Signed-off-by: Emanuele Giuseppe Esposito <eesposit@redhat.com>
---
 block.c                            | 28 ++++++++++++++++------------
 include/block/block-global-state.h |  2 +-
 include/block/block_int-common.h   |  3 ++-
 3 files changed, 19 insertions(+), 14 deletions(-)

diff --git a/block.c b/block.c
index c80e49009a..c02a628336 100644
--- a/block.c
+++ b/block.c
@@ -109,7 +109,7 @@ static void bdrv_reopen_abort(BDRVReopenState *reopen_state);
 static bool bdrv_backing_overridden(BlockDriverState *bs);
 
 static bool bdrv_change_aio_context(BlockDriverState *bs, AioContext *ctx,
-                                    GSList **visited, Transaction *tran,
+                                    GHashTable *visited, Transaction *tran,
                                     Error **errp);
 
 /* If non-zero, use only whitelisted block drivers */
@@ -7444,14 +7444,15 @@ typedef struct BdrvStateSetAioContext {
 } BdrvStateSetAioContext;
 
 static bool bdrv_parent_change_aio_context(BdrvChild *c, AioContext *ctx,
-                                           GSList **visited, Transaction *tran,
+                                           GHashTable *visited,
+                                           Transaction *tran,
                                            Error **errp)
 {
     GLOBAL_STATE_CODE();
-    if (g_slist_find(*visited, c)) {
+    if (g_hash_table_contains(visited, c)) {
         return true;
     }
-    *visited = g_slist_prepend(*visited, c);
+    g_hash_table_add(visited, c);
 
     /*
      * A BdrvChildClass that doesn't handle AioContext changes cannot
@@ -7482,14 +7483,14 @@ bool bdrv_child_can_set_aio_context(BdrvChild *c, AioContext *ctx,
 }
 
 bool bdrv_child_change_aio_context(BdrvChild *c, AioContext *ctx,
-                                   GSList **visited, Transaction *tran,
+                                   GHashTable *visited, Transaction *tran,
                                    Error **errp)
 {
     GLOBAL_STATE_CODE();
-    if (g_slist_find(*visited, c)) {
+    if (g_hash_table_contains(visited, c)) {
         return true;
     }
-    *visited = g_slist_prepend(*visited, c);
+    g_hash_table_add(visited, c);
     return bdrv_change_aio_context(c->bs, ctx, visited, tran, errp);
 }
 
@@ -7561,7 +7562,7 @@ static TransactionActionDrv set_aio_context = {
  * responsible for freeing the list afterwards.
  */
 static bool bdrv_change_aio_context(BlockDriverState *bs, AioContext *ctx,
-                                    GSList **visited, Transaction *tran,
+                                    GHashTable *visited, Transaction *tran,
                                     Error **errp)
 {
     BdrvChild *c;
@@ -7646,16 +7647,19 @@ int bdrv_child_try_change_aio_context(BlockDriverState *bs, AioContext *ctx,
                                       BdrvChild *ignore_child, Error **errp)
 {
     Transaction *tran;
-    GSList *visited;
+    GHashTable *visited;
     int ret;
     AioContext *old_context = bdrv_get_aio_context(bs);
     GLOBAL_STATE_CODE();
 
     /* Recursion phase: go through all nodes of the graph */
     tran = tran_new();
-    visited = ignore_child ? g_slist_prepend(NULL, ignore_child) : NULL;
-    ret = bdrv_change_aio_context(bs, ctx, &visited, tran, errp);
-    g_slist_free(visited);
+    visited = g_hash_table_new(NULL, NULL);
+    if (ignore_child) {
+        g_hash_table_add(visited, ignore_child);
+    }
+    ret = bdrv_change_aio_context(bs, ctx, visited, tran, errp);
+    g_hash_table_destroy(visited);
 
     /* Linear phase: go through all callbacks collected in the transaction */
 
diff --git a/include/block/block-global-state.h b/include/block/block-global-state.h
index fdcb81a175..ceecf0aa8e 100644
--- a/include/block/block-global-state.h
+++ b/include/block/block-global-state.h
@@ -230,7 +230,7 @@ bool bdrv_can_set_aio_context(BlockDriverState *bs, AioContext *ctx,
 AioContext *bdrv_child_get_parent_aio_context(BdrvChild *c);
 
 bool bdrv_child_change_aio_context(BdrvChild *c, AioContext *ctx,
-                                   GSList **visited, Transaction *tran,
+                                   GHashTable *visited, Transaction *tran,
                                    Error **errp);
 int bdrv_child_try_change_aio_context(BlockDriverState *bs, AioContext *ctx,
                                       BdrvChild *ignore_child, Error **errp);
diff --git a/include/block/block_int-common.h b/include/block/block_int-common.h
index 43828cf74f..c639873487 100644
--- a/include/block/block_int-common.h
+++ b/include/block/block_int-common.h
@@ -897,7 +897,8 @@ struct BdrvChildClass {
     void (*set_aio_ctx)(BdrvChild *child, AioContext *ctx, GSList **ignore);
 
     bool (*change_aio_ctx)(BdrvChild *child, AioContext *ctx,
-                           GSList **visited, Transaction *tran, Error **errp);
+                           GHashTable *visited, Transaction *tran,
+                           Error **errp);
 
     AioContext *(*get_parent_aio_context)(BdrvChild *child);
 
-- 
2.31.1