[PATCH] 9pfs: use GHashMap for fid table

[PATCH] 9pfs: use GHashMap for fid table

[Linus Heckemann]

The previous implementation would iterate over the fid table for
lookup operations, resulting in an operation with O(n) complexity on
the number of open files and poor cache locality -- for nearly every
open, stat, read, write, etc operation.

This change uses a hashtable for this instead, significantly improving
the performance of the 9p filesystem. The runtime of NixOS's simple
installer test, which copies ~122k files totalling ~1.8GiB from 9p,
decreased by a factor of about 10.

Signed-off-by: Linus Heckemann <git@sphalerite.org>
---
 hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------
 hw/9pfs/9p.h |   2 +-
 2 files changed, 69 insertions(+), 63 deletions(-)

diff --git a/hw/9pfs/9p.c b/hw/9pfs/9p.c
index aebadeaa03..ff466afe39 100644
--- a/hw/9pfs/9p.c
+++ b/hw/9pfs/9p.c
@@ -282,33 +282,31 @@ static V9fsFidState *coroutine_fn get_fid(V9fsPDU *pdu, int32_t fid)
     V9fsFidState *f;
     V9fsState *s = pdu->s;
 
-    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
-        BUG_ON(f->clunked);
-        if (f->fid == fid) {
-            /*
-             * Update the fid ref upfront so that
-             * we don't get reclaimed when we yield
-             * in open later.
-             */
-            f->ref++;
-            /*
-             * check whether we need to reopen the
-             * file. We might have closed the fd
-             * while trying to free up some file
-             * descriptors.
-             */
-            err = v9fs_reopen_fid(pdu, f);
-            if (err < 0) {
-                f->ref--;
-                return NULL;
-            }
-            /*
-             * Mark the fid as referenced so that the LRU
-             * reclaim won't close the file descriptor
-             */
-            f->flags |= FID_REFERENCED;
-            return f;
+    f = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
+    if (f) {
+        /*
+         * Update the fid ref upfront so that
+         * we don't get reclaimed when we yield
+         * in open later.
+         */
+        f->ref++;
+        /*
+         * check whether we need to reopen the
+         * file. We might have closed the fd
+         * while trying to free up some file
+         * descriptors.
+         */
+        err = v9fs_reopen_fid(pdu, f);
+        if (err < 0) {
+            f->ref--;
+            return NULL;
         }
+        /*
+         * Mark the fid as referenced so that the LRU
+         * reclaim won't close the file descriptor
+         */
+        f->flags |= FID_REFERENCED;
+        return f;
     }
     return NULL;
 }
@@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid)
 {
     V9fsFidState *f;
 
-    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
+    if (g_hash_table_contains(s->fids, GINT_TO_POINTER(fid))) {
         /* If fid is already there return NULL */
-        BUG_ON(f->clunked);
-        if (f->fid == fid) {
-            return NULL;
-        }
+        return NULL;
     }
     f = g_new0(V9fsFidState, 1);
     f->fid = fid;
@@ -333,7 +328,7 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid)
      * reclaim won't close the file descriptor
      */
     f->flags |= FID_REFERENCED;
-    QSIMPLEQ_INSERT_TAIL(&s->fid_list, f, next);
+    g_hash_table_insert(s->fids, GINT_TO_POINTER(fid), f);
 
     v9fs_readdir_init(s->proto_version, &f->fs.dir);
     v9fs_readdir_init(s->proto_version, &f->fs_reclaim.dir);
@@ -424,12 +419,11 @@ static V9fsFidState *clunk_fid(V9fsState *s, int32_t fid)
 {
     V9fsFidState *fidp;
 
-    QSIMPLEQ_FOREACH(fidp, &s->fid_list, next) {
-        if (fidp->fid == fid) {
-            QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
-            fidp->clunked = true;
-            return fidp;
-        }
+    fidp = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
+    if (fidp) {
+        g_hash_table_remove(s->fids, GINT_TO_POINTER(fid));
+        fidp->clunked = true;
+        return fidp;
     }
     return NULL;
 }
@@ -439,10 +433,15 @@ void coroutine_fn v9fs_reclaim_fd(V9fsPDU *pdu)
     int reclaim_count = 0;
     V9fsState *s = pdu->s;
     V9fsFidState *f;
+
+    GHashTableIter iter;
+    gpointer fid;
+    g_hash_table_iter_init(&iter, s->fids);
+
     QSLIST_HEAD(, V9fsFidState) reclaim_list =
         QSLIST_HEAD_INITIALIZER(reclaim_list);
 
-    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
+    while (g_hash_table_iter_next(&iter, &fid, (void **) &f)) {
         /*
          * Unlink fids cannot be reclaimed. Check
          * for them and skip them. Also skip fids
@@ -518,12 +517,12 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
 {
     int err;
     V9fsState *s = pdu->s;
-    V9fsFidState *fidp, *fidp_next;
+    V9fsFidState *fidp;
+    gpointer fid;
+
+    GHashTableIter iter;
+    g_hash_table_iter_init(&iter, s->fids);
 
-    fidp = QSIMPLEQ_FIRST(&s->fid_list);
-    if (!fidp) {
-        return 0;
-    }
 
     /*
      * v9fs_reopen_fid() can yield : a reference on the fid must be held
@@ -534,7 +533,13 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
      * iteration after we could get a reference on the next fid. Start with
      * the first one.
      */
-    for (fidp->ref++; fidp; fidp = fidp_next) {
+    while (g_hash_table_iter_next(&iter, &fid, (void **) &fidp)) {
+        /*
+         * Ensure the fid survives a potential clunk request during
+         * put_fid() below and v9fs_reopen_fid() in the next iteration.
+         */
+        fidp->ref++;
+
         if (fidp->path.size == path->size &&
             !memcmp(fidp->path.data, path->data, path->size)) {
             /* Mark the fid non reclaimable. */
@@ -548,16 +553,6 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
             }
         }
 
-        fidp_next = QSIMPLEQ_NEXT(fidp, next);
-
-        if (fidp_next) {
-            /*
-             * Ensure the next fid survives a potential clunk request during
-             * put_fid() below and v9fs_reopen_fid() in the next iteration.
-             */
-            fidp_next->ref++;
-        }
-
         /* We're done with this fid */
         put_fid(pdu, fidp);
     }
@@ -570,18 +565,20 @@ static void coroutine_fn virtfs_reset(V9fsPDU *pdu)
     V9fsState *s = pdu->s;
     V9fsFidState *fidp;
 
+    gpointer fid;
+    GHashTableIter iter;
+    g_hash_table_iter_init(&iter, s->fids);
+
     /* Free all fids */
-    while (!QSIMPLEQ_EMPTY(&s->fid_list)) {
-        /* Get fid */
-        fidp = QSIMPLEQ_FIRST(&s->fid_list);
+    while (g_hash_table_iter_next(&iter, &fid, (void **) &fidp)) {
         fidp->ref++;
 
         /* Clunk fid */
-        QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
         fidp->clunked = true;
 
         put_fid(pdu, fidp);
     }
+    g_hash_table_remove_all(s->fids);
 }
 
 #define P9_QID_TYPE_DIR         0x80
@@ -3206,6 +3203,9 @@ static int coroutine_fn v9fs_complete_rename(V9fsPDU *pdu, V9fsFidState *fidp,
     V9fsState *s = pdu->s;
     V9fsFidState *dirfidp = NULL;
 
+    GHashTableIter iter;
+    gpointer fid;
+
     v9fs_path_init(&new_path);
     if (newdirfid != -1) {
         dirfidp = get_fid(pdu, newdirfid);
@@ -3238,11 +3238,13 @@ static int coroutine_fn v9fs_complete_rename(V9fsPDU *pdu, V9fsFidState *fidp,
     if (err < 0) {
         goto out;
     }
+
     /*
      * Fixup fid's pointing to the old name to
      * start pointing to the new name
      */
-    QSIMPLEQ_FOREACH(tfidp, &s->fid_list, next) {
+    g_hash_table_iter_init(&iter, s->fids);
+    while (g_hash_table_iter_next(&iter, &fid, (void **) &tfidp)) {
         if (v9fs_path_is_ancestor(&fidp->path, &tfidp->path)) {
             /* replace the name */
             v9fs_fix_path(&tfidp->path, &new_path, strlen(fidp->path.data));
@@ -3321,6 +3323,9 @@ static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir,
     V9fsState *s = pdu->s;
     int err;
 
+    GHashTableIter iter;
+    gpointer fid;
+
     v9fs_path_init(&oldpath);
     v9fs_path_init(&newpath);
     err = v9fs_co_name_to_path(pdu, olddir, old_name->data, &oldpath);
@@ -3336,7 +3341,8 @@ static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir,
      * Fixup fid's pointing to the old name to
      * start pointing to the new name
      */
-    QSIMPLEQ_FOREACH(tfidp, &s->fid_list, next) {
+    g_hash_table_iter_init(&iter, s->fids);
+    while (g_hash_table_iter_next(&iter, &fid, (void **) &tfidp)) {
         if (v9fs_path_is_ancestor(&oldpath, &tfidp->path)) {
             /* replace the name */
             v9fs_fix_path(&tfidp->path, &newpath, strlen(oldpath.data));
@@ -4226,7 +4232,7 @@ int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t,
     s->ctx.fmode = fse->fmode;
     s->ctx.dmode = fse->dmode;
 
-    QSIMPLEQ_INIT(&s->fid_list);
+    s->fids = g_hash_table_new(NULL, NULL);
     qemu_co_rwlock_init(&s->rename_lock);
 
     if (s->ops->init(&s->ctx, errp) < 0) {
diff --git a/hw/9pfs/9p.h b/hw/9pfs/9p.h
index 994f952600..10fd2076c2 100644
--- a/hw/9pfs/9p.h
+++ b/hw/9pfs/9p.h
@@ -339,7 +339,7 @@ typedef struct {
 struct V9fsState {
     QLIST_HEAD(, V9fsPDU) free_list;
     QLIST_HEAD(, V9fsPDU) active_list;
-    QSIMPLEQ_HEAD(, V9fsFidState) fid_list;
+    GHashTable *fids;
     FileOperations *ops;
     FsContext ctx;
     char *tag;
-- 
2.36.0

Re: [PATCH] 9pfs: use GHashMap for fid table

[Philippe Mathieu-Daudé via]

Hi Linus,

On 3/9/22 17:03, Linus Heckemann wrote:
> The previous implementation would iterate over the fid table for
> lookup operations, resulting in an operation with O(n) complexity on
> the number of open files and poor cache locality -- for nearly every
> open, stat, read, write, etc operation.
> 
> This change uses a hashtable for this instead, significantly improving
> the performance of the 9p filesystem. The runtime of NixOS's simple
> installer test, which copies ~122k files totalling ~1.8GiB from 9p,
> decreased by a factor of about 10.
> 
> Signed-off-by: Linus Heckemann <git@sphalerite.org>
> ---
>   hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------
>   hw/9pfs/9p.h |   2 +-
>   2 files changed, 69 insertions(+), 63 deletions(-)

> @@ -424,12 +419,11 @@ static V9fsFidState *clunk_fid(V9fsState *s, int32_t fid)
>   {
>       V9fsFidState *fidp;
>   
> -    QSIMPLEQ_FOREACH(fidp, &s->fid_list, next) {
> -        if (fidp->fid == fid) {
> -            QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
> -            fidp->clunked = true;
> -            return fidp;
> -        }
> +    fidp = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
> +    if (fidp) {
> +        g_hash_table_remove(s->fids, GINT_TO_POINTER(fid));
> +        fidp->clunked = true;
> +        return fidp;
>       }
>       return NULL;
>   }
> @@ -439,10 +433,15 @@ void coroutine_fn v9fs_reclaim_fd(V9fsPDU *pdu)
>       int reclaim_count = 0;
>       V9fsState *s = pdu->s;
>       V9fsFidState *f;
> +

Style nitpicking: we don't restrict to C89 but still declare variables
at the beginning of functions, so please move this new line ...

> +    GHashTableIter iter;
> +    gpointer fid;

... here.

> +    g_hash_table_iter_init(&iter, s->fids);
> +
>       QSLIST_HEAD(, V9fsFidState) reclaim_list =
>           QSLIST_HEAD_INITIALIZER(reclaim_list);
>   
> -    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
> +    while (g_hash_table_iter_next(&iter, &fid, (void **) &f)) {

Please cast to (gpointer *) instead.

>           /*
>            * Unlink fids cannot be reclaimed. Check
>            * for them and skip them. Also skip fids
> @@ -518,12 +517,12 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
>   {
>       int err;
>       V9fsState *s = pdu->s;
> -    V9fsFidState *fidp, *fidp_next;
> +    V9fsFidState *fidp;
> +    gpointer fid;
> +
> +    GHashTableIter iter;

Style.

> +    g_hash_table_iter_init(&iter, s->fids);
>   
> -    fidp = QSIMPLEQ_FIRST(&s->fid_list);
> -    if (!fidp) {
> -        return 0;
> -    }
>   
>       /*
>        * v9fs_reopen_fid() can yield : a reference on the fid must be held
> @@ -534,7 +533,13 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
>        * iteration after we could get a reference on the next fid. Start with
>        * the first one.
>        */
> -    for (fidp->ref++; fidp; fidp = fidp_next) {
> +    while (g_hash_table_iter_next(&iter, &fid, (void **) &fidp)) {

gpointer *.

> +        /*
> +         * Ensure the fid survives a potential clunk request during
> +         * put_fid() below and v9fs_reopen_fid() in the next iteration.
> +         */
> +        fidp->ref++;
> +
>           if (fidp->path.size == path->size &&
>               !memcmp(fidp->path.data, path->data, path->size)) {
>               /* Mark the fid non reclaimable. */
> @@ -548,16 +553,6 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
>               }
>           }
>   
> -        fidp_next = QSIMPLEQ_NEXT(fidp, next);
> -
> -        if (fidp_next) {
> -            /*
> -             * Ensure the next fid survives a potential clunk request during
> -             * put_fid() below and v9fs_reopen_fid() in the next iteration.
> -             */
> -            fidp_next->ref++;
> -        }
> -
>           /* We're done with this fid */
>           put_fid(pdu, fidp);
>       }
> @@ -570,18 +565,20 @@ static void coroutine_fn virtfs_reset(V9fsPDU *pdu)
>       V9fsState *s = pdu->s;
>       V9fsFidState *fidp;
>   
> +    gpointer fid;
> +    GHashTableIter iter;

Style.

> +    g_hash_table_iter_init(&iter, s->fids);
> +
>       /* Free all fids */
> -    while (!QSIMPLEQ_EMPTY(&s->fid_list)) {
> -        /* Get fid */
> -        fidp = QSIMPLEQ_FIRST(&s->fid_list);
> +    while (g_hash_table_iter_next(&iter, &fid, (void **) &fidp)) {

gpointer *.

>           fidp->ref++;
>   
>           /* Clunk fid */
> -        QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
>           fidp->clunked = true;
>   
>           put_fid(pdu, fidp);
>       }
> +    g_hash_table_remove_all(s->fids);
>   }
>   
>   #define P9_QID_TYPE_DIR         0x80
> @@ -3206,6 +3203,9 @@ static int coroutine_fn v9fs_complete_rename(V9fsPDU *pdu, V9fsFidState *fidp,
>       V9fsState *s = pdu->s;
>       V9fsFidState *dirfidp = NULL;
>   

Please remove this extra new line.

> +    GHashTableIter iter;
> +    gpointer fid;
> +
>       v9fs_path_init(&new_path);
>       if (newdirfid != -1) {
>           dirfidp = get_fid(pdu, newdirfid);
> @@ -3238,11 +3238,13 @@ static int coroutine_fn v9fs_complete_rename(V9fsPDU *pdu, V9fsFidState *fidp,
>       if (err < 0) {
>           goto out;
>       }
> +
>       /*
>        * Fixup fid's pointing to the old name to
>        * start pointing to the new name
>        */
> -    QSIMPLEQ_FOREACH(tfidp, &s->fid_list, next) {
> +    g_hash_table_iter_init(&iter, s->fids);
> +    while (g_hash_table_iter_next(&iter, &fid, (void **) &tfidp)) {
>           if (v9fs_path_is_ancestor(&fidp->path, &tfidp->path)) {
>               /* replace the name */
>               v9fs_fix_path(&tfidp->path, &new_path, strlen(fidp->path.data));
> @@ -3321,6 +3323,9 @@ static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir,
>       V9fsState *s = pdu->s;
>       int err;
>   

Extra new line.

> +    GHashTableIter iter;
> +    gpointer fid;
> +
>       v9fs_path_init(&oldpath);
>       v9fs_path_init(&newpath);
>       err = v9fs_co_name_to_path(pdu, olddir, old_name->data, &oldpath);
> @@ -3336,7 +3341,8 @@ static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir,
>        * Fixup fid's pointing to the old name to
>        * start pointing to the new name
>        */
> -    QSIMPLEQ_FOREACH(tfidp, &s->fid_list, next) {
> +    g_hash_table_iter_init(&iter, s->fids);
> +    while (g_hash_table_iter_next(&iter, &fid, (void **) &tfidp)) {

gpointer *.

>           if (v9fs_path_is_ancestor(&oldpath, &tfidp->path)) {
>               /* replace the name */
>               v9fs_fix_path(&tfidp->path, &newpath, strlen(oldpath.data));
> @@ -4226,7 +4232,7 @@ int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t,
>       s->ctx.fmode = fse->fmode;
>       s->ctx.dmode = fse->dmode;
>   
> -    QSIMPLEQ_INIT(&s->fid_list);
> +    s->fids = g_hash_table_new(NULL, NULL);
>       qemu_co_rwlock_init(&s->rename_lock);

Minor style nitpicking comments, otherwise:
Reviewed-by: Philippe Mathieu-Daudé <f4bug@amsat.org>

Re: [PATCH] 9pfs: use GHashMap for fid table

[Christian Schoenebeck]

On Samstag, 3. September 2022 17:03:27 CEST Linus Heckemann wrote:
> The previous implementation would iterate over the fid table for
> lookup operations, resulting in an operation with O(n) complexity on
> the number of open files and poor cache locality -- for nearly every
> open, stat, read, write, etc operation.

Oh yes, I had this on my TODO list for a long time. Thanks for the effort 
Linus!

> This change uses a hashtable for this instead, significantly improving
> the performance of the 9p filesystem. The runtime of NixOS's simple
> installer test, which copies ~122k files totalling ~1.8GiB from 9p,
> decreased by a factor of about 10.

Wow, even more than I expected. Nice!

I have a feeling that this will also fix the massive slow downs that were seen 
after running for a long time. Because I think that slow down was because a 
large amount of fids were accumulated over time, where this O(n) issue hurts 
more noticably.

Some remarks below ...

> Signed-off-by: Linus Heckemann <git@sphalerite.org>
> ---
>  hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------
>  hw/9pfs/9p.h |   2 +-
>  2 files changed, 69 insertions(+), 63 deletions(-)
> 
> diff --git a/hw/9pfs/9p.c b/hw/9pfs/9p.c
> index aebadeaa03..ff466afe39 100644
> --- a/hw/9pfs/9p.c
> +++ b/hw/9pfs/9p.c
> @@ -282,33 +282,31 @@ static V9fsFidState *coroutine_fn get_fid(V9fsPDU
> *pdu, int32_t fid) V9fsFidState *f;
>      V9fsState *s = pdu->s;
> 
> -    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
> -        BUG_ON(f->clunked);
> -        if (f->fid == fid) {
> -            /*
> -             * Update the fid ref upfront so that
> -             * we don't get reclaimed when we yield
> -             * in open later.
> -             */
> -            f->ref++;
> -            /*
> -             * check whether we need to reopen the
> -             * file. We might have closed the fd
> -             * while trying to free up some file
> -             * descriptors.
> -             */
> -            err = v9fs_reopen_fid(pdu, f);
> -            if (err < 0) {
> -                f->ref--;
> -                return NULL;
> -            }
> -            /*
> -             * Mark the fid as referenced so that the LRU
> -             * reclaim won't close the file descriptor
> -             */
> -            f->flags |= FID_REFERENCED;
> -            return f;
> +    f = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
> +    if (f) {
> +        /*
> +         * Update the fid ref upfront so that
> +         * we don't get reclaimed when we yield
> +         * in open later.
> +         */
> +        f->ref++;
> +        /*
> +         * check whether we need to reopen the
> +         * file. We might have closed the fd
> +         * while trying to free up some file
> +         * descriptors.
> +         */
> +        err = v9fs_reopen_fid(pdu, f);
> +        if (err < 0) {
> +            f->ref--;
> +            return NULL;
>          }
> +        /*
> +         * Mark the fid as referenced so that the LRU
> +         * reclaim won't close the file descriptor
> +         */
> +        f->flags |= FID_REFERENCED;
> +        return f;
>      }
>      return NULL;
>  }
> @@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t
> fid) {
>      V9fsFidState *f;
> 
> -    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
> +    if (g_hash_table_contains(s->fids, GINT_TO_POINTER(fid))) {
>          /* If fid is already there return NULL */
> -        BUG_ON(f->clunked);
> -        if (f->fid == fid) {
> -            return NULL;
> -        }
> +        return NULL;

Probably retaining BUG_ON(f->clunked) here?

>      }
>      f = g_new0(V9fsFidState, 1);
>      f->fid = fid;
> @@ -333,7 +328,7 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t
> fid) * reclaim won't close the file descriptor
>       */
>      f->flags |= FID_REFERENCED;
> -    QSIMPLEQ_INSERT_TAIL(&s->fid_list, f, next);
> +    g_hash_table_insert(s->fids, GINT_TO_POINTER(fid), f);
> 
>      v9fs_readdir_init(s->proto_version, &f->fs.dir);
>      v9fs_readdir_init(s->proto_version, &f->fs_reclaim.dir);
> @@ -424,12 +419,11 @@ static V9fsFidState *clunk_fid(V9fsState *s, int32_t
> fid) {
>      V9fsFidState *fidp;
> 
> -    QSIMPLEQ_FOREACH(fidp, &s->fid_list, next) {
> -        if (fidp->fid == fid) {
> -            QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
> -            fidp->clunked = true;
> -            return fidp;
> -        }
> +    fidp = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
> +    if (fidp) {
> +        g_hash_table_remove(s->fids, GINT_TO_POINTER(fid));
> +        fidp->clunked = true;
> +        return fidp;

We can't get rid of the double lookup here, can we? Surprisingly I don't find 
a lookup function on the iterator based API.

>      }
>      return NULL;
>  }
> @@ -439,10 +433,15 @@ void coroutine_fn v9fs_reclaim_fd(V9fsPDU *pdu)
>      int reclaim_count = 0;
>      V9fsState *s = pdu->s;
>      V9fsFidState *f;
> +
> +    GHashTableIter iter;
> +    gpointer fid;
> +    g_hash_table_iter_init(&iter, s->fids);
> +
>      QSLIST_HEAD(, V9fsFidState) reclaim_list =
>          QSLIST_HEAD_INITIALIZER(reclaim_list);
> 
> -    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
> +    while (g_hash_table_iter_next(&iter, &fid, (void **) &f)) {
>          /*
>           * Unlink fids cannot be reclaimed. Check
>           * for them and skip them. Also skip fids
> @@ -518,12 +517,12 @@ static int coroutine_fn
> v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path) {
>      int err;
>      V9fsState *s = pdu->s;
> -    V9fsFidState *fidp, *fidp_next;
> +    V9fsFidState *fidp;
> +    gpointer fid;
> +
> +    GHashTableIter iter;
> +    g_hash_table_iter_init(&iter, s->fids);
> 
> -    fidp = QSIMPLEQ_FIRST(&s->fid_list);
> -    if (!fidp) {
> -        return 0;
> -    }
> 
>      /*
>       * v9fs_reopen_fid() can yield : a reference on the fid must be held
> @@ -534,7 +533,13 @@ static int coroutine_fn
> v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path) * iteration after we
> could get a reference on the next fid. Start with * the first one.
>       */
> -    for (fidp->ref++; fidp; fidp = fidp_next) {
> +    while (g_hash_table_iter_next(&iter, &fid, (void **) &fidp)) {

Too bad that there's apparently no macro based g_hash_table_foreach(), that 
would have made the code a bit cleaner and shorter than using an iterator 
while loop, but OK.

Best regards,
Christian Schoenebeck

> +        /*
> +         * Ensure the fid survives a potential clunk request during
> +         * put_fid() below and v9fs_reopen_fid() in the next iteration.
> +         */
> +        fidp->ref++;
> +
>          if (fidp->path.size == path->size &&
>              !memcmp(fidp->path.data, path->data, path->size)) {
>              /* Mark the fid non reclaimable. */
> @@ -548,16 +553,6 @@ static int coroutine_fn
> v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path) }
>          }
> 
> -        fidp_next = QSIMPLEQ_NEXT(fidp, next);
> -
> -        if (fidp_next) {
> -            /*
> -             * Ensure the next fid survives a potential clunk request
> during -             * put_fid() below and v9fs_reopen_fid() in the next
> iteration. -             */
> -            fidp_next->ref++;
> -        }
> -
>          /* We're done with this fid */
>          put_fid(pdu, fidp);
>      }
> @@ -570,18 +565,20 @@ static void coroutine_fn virtfs_reset(V9fsPDU *pdu)
>      V9fsState *s = pdu->s;
>      V9fsFidState *fidp;
> 
> +    gpointer fid;
> +    GHashTableIter iter;
> +    g_hash_table_iter_init(&iter, s->fids);
> +
>      /* Free all fids */
> -    while (!QSIMPLEQ_EMPTY(&s->fid_list)) {
> -        /* Get fid */
> -        fidp = QSIMPLEQ_FIRST(&s->fid_list);
> +    while (g_hash_table_iter_next(&iter, &fid, (void **) &fidp)) {
>          fidp->ref++;
> 
>          /* Clunk fid */
> -        QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
>          fidp->clunked = true;
> 
>          put_fid(pdu, fidp);
>      }
> +    g_hash_table_remove_all(s->fids);
>  }
> 
>  #define P9_QID_TYPE_DIR         0x80
> @@ -3206,6 +3203,9 @@ static int coroutine_fn v9fs_complete_rename(V9fsPDU
> *pdu, V9fsFidState *fidp, V9fsState *s = pdu->s;
>      V9fsFidState *dirfidp = NULL;
> 
> +    GHashTableIter iter;
> +    gpointer fid;
> +
>      v9fs_path_init(&new_path);
>      if (newdirfid != -1) {
>          dirfidp = get_fid(pdu, newdirfid);
> @@ -3238,11 +3238,13 @@ static int coroutine_fn v9fs_complete_rename(V9fsPDU
> *pdu, V9fsFidState *fidp, if (err < 0) {
>          goto out;
>      }
> +
>      /*
>       * Fixup fid's pointing to the old name to
>       * start pointing to the new name
>       */
> -    QSIMPLEQ_FOREACH(tfidp, &s->fid_list, next) {
> +    g_hash_table_iter_init(&iter, s->fids);
> +    while (g_hash_table_iter_next(&iter, &fid, (void **) &tfidp)) {
>          if (v9fs_path_is_ancestor(&fidp->path, &tfidp->path)) {
>              /* replace the name */
>              v9fs_fix_path(&tfidp->path, &new_path,
> strlen(fidp->path.data)); @@ -3321,6 +3323,9 @@ static int coroutine_fn
> v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir, V9fsState *s = pdu->s;
>      int err;
> 
> +    GHashTableIter iter;
> +    gpointer fid;
> +
>      v9fs_path_init(&oldpath);
>      v9fs_path_init(&newpath);
>      err = v9fs_co_name_to_path(pdu, olddir, old_name->data, &oldpath);
> @@ -3336,7 +3341,8 @@ static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU
> *pdu, V9fsPath *olddir, * Fixup fid's pointing to the old name to
>       * start pointing to the new name
>       */
> -    QSIMPLEQ_FOREACH(tfidp, &s->fid_list, next) {
> +    g_hash_table_iter_init(&iter, s->fids);
> +    while (g_hash_table_iter_next(&iter, &fid, (void **) &tfidp)) {
>          if (v9fs_path_is_ancestor(&oldpath, &tfidp->path)) {
>              /* replace the name */
>              v9fs_fix_path(&tfidp->path, &newpath, strlen(oldpath.data));
> @@ -4226,7 +4232,7 @@ int v9fs_device_realize_common(V9fsState *s, const
> V9fsTransport *t, s->ctx.fmode = fse->fmode;
>      s->ctx.dmode = fse->dmode;
> 
> -    QSIMPLEQ_INIT(&s->fid_list);
> +    s->fids = g_hash_table_new(NULL, NULL);
>      qemu_co_rwlock_init(&s->rename_lock);
> 
>      if (s->ops->init(&s->ctx, errp) < 0) {
> diff --git a/hw/9pfs/9p.h b/hw/9pfs/9p.h
> index 994f952600..10fd2076c2 100644
> --- a/hw/9pfs/9p.h
> +++ b/hw/9pfs/9p.h
> @@ -339,7 +339,7 @@ typedef struct {
>  struct V9fsState {
>      QLIST_HEAD(, V9fsPDU) free_list;
>      QLIST_HEAD(, V9fsPDU) active_list;
> -    QSIMPLEQ_HEAD(, V9fsFidState) fid_list;
> +    GHashTable *fids;
>      FileOperations *ops;
>      FsContext ctx;
>      char *tag;

Re: [PATCH] 9pfs: use GHashMap for fid table

[Daniel P. Berrangé]

In $SUBJECT it is called GHashTable, not GHashMap

On Sat, Sep 03, 2022 at 05:03:27PM +0200, Linus Heckemann wrote:
> The previous implementation would iterate over the fid table for
> lookup operations, resulting in an operation with O(n) complexity on
> the number of open files and poor cache locality -- for nearly every
> open, stat, read, write, etc operation.
> 
> This change uses a hashtable for this instead, significantly improving
> the performance of the 9p filesystem. The runtime of NixOS's simple
> installer test, which copies ~122k files totalling ~1.8GiB from 9p,
> decreased by a factor of about 10.
> 
> Signed-off-by: Linus Heckemann <git@sphalerite.org>
> ---
>  hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------
>  hw/9pfs/9p.h |   2 +-
>  2 files changed, 69 insertions(+), 63 deletions(-)


With regards,
Daniel
-- 
|: https://berrange.com      -o-    https://www.flickr.com/photos/dberrange :|
|: https://libvirt.org         -o-            https://fstop138.berrange.com :|
|: https://entangle-photo.org    -o-    https://www.instagram.com/dberrange :|

Re: [PATCH] 9pfs: use GHashMap for fid table

[Linus Heckemann]

Hi all, thanks for your reviews.

> @@ -4226,7 +4232,7 @@ int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t,
>      s->ctx.fmode = fse->fmode;
>      s->ctx.dmode = fse->dmode;
> 
> -    QSIMPLEQ_INIT(&s->fid_list);
> +    s->fids = g_hash_table_new(NULL, NULL);
>      qemu_co_rwlock_init(&s->rename_lock);
> 
>      if (s->ops->init(&s->ctx, errp) < 0) {

I noticed that the hash table may be leaked as is. I'll address this in
the next submission.


Philippe Mathieu-Daudé <f4bug@amsat.org> writes:
> [Style nitpicking]

Applied these changes and will include them in the next version of the patch.

Christian Schoenebeck <qemu_oss@crudebyte.com> writes:
> > @@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t
> > fid) {
> >      V9fsFidState *f;
> > 
> > -    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
> > +    if (g_hash_table_contains(s->fids, GINT_TO_POINTER(fid))) {
> >          /* If fid is already there return NULL */
> > -        BUG_ON(f->clunked);
> > -        if (f->fid == fid) {
> > -            return NULL;
> > -        }
> > +        return NULL;
>
> Probably retaining BUG_ON(f->clunked) here?

I decided not to since this was a sanity check that was happening for
_each_ fid, but only up to the one we were looking for. This seemed
inconsistent and awkward to me, so I dropped it completely (and the
invariant that no clunked fids remain in the table still seems to hold
-- it's fairly trivial to check, in that the clunked flag is only set
in two places, both of which also remove the map entry). My preference
would be to leave it out, but I'd also be fine with restoring it for
just the one we're looking for, or maybe moving the check to when we're
iterating over the whole table, e.g. in v9fs_reclaim_fd. Thoughts?

> > @@ -424,12 +419,11 @@ static V9fsFidState *clunk_fid(V9fsState *s, int32_t
> > fid) {
> >      V9fsFidState *fidp;
> > 
> > -    QSIMPLEQ_FOREACH(fidp, &s->fid_list, next) {
> > -        if (fidp->fid == fid) {
> > -            QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
> > -            fidp->clunked = true;
> > -            return fidp;
> > -        }
> > +    fidp = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
> > +    if (fidp) {
> > +        g_hash_table_remove(s->fids, GINT_TO_POINTER(fid));
> > +        fidp->clunked = true;
> > +        return fidp;
>
> We can't get rid of the double lookup here, can we? Surprisingly I don't find 
> a lookup function on the iterator based API.

It seems you're not the only one who had that idea:
https://gitlab.gnome.org/GNOME/glib/-/issues/613

In this case, I think an extended remove function which returns the
values that were present would be even nicer. But neither exists at this
time (and that issue is pretty old), I guess we're stuck with this for
now.


Daniel P. Berrangé writes:
> In $SUBJECT it is called GHashTable, not GHashMap

Indeed, good catch. Will fix in the next version.

Linus

Re: [PATCH] 9pfs: use GHashMap for fid table

[Christian Schoenebeck]

On Montag, 5. September 2022 10:51:10 CEST Linus Heckemann wrote:
> Hi all, thanks for your reviews.
> 
> > @@ -4226,7 +4232,7 @@ int v9fs_device_realize_common(V9fsState *s, const
> > V9fsTransport *t,> 
> >      s->ctx.fmode = fse->fmode;
> >      s->ctx.dmode = fse->dmode;
> > 
> > -    QSIMPLEQ_INIT(&s->fid_list);
> > +    s->fids = g_hash_table_new(NULL, NULL);
> > 
> >      qemu_co_rwlock_init(&s->rename_lock);
> >      
> >      if (s->ops->init(&s->ctx, errp) < 0) {
> 
> I noticed that the hash table may be leaked as is. I'll address this in
> the next submission.
> 
> Philippe Mathieu-Daudé <f4bug@amsat.org> writes:
> > [Style nitpicking]
> 
> Applied these changes and will include them in the next version of the
> patch.
> Christian Schoenebeck <qemu_oss@crudebyte.com> writes:
> > > @@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s,
> > > int32_t
> > > fid) {
> > > 
> > >      V9fsFidState *f;
> > > 
> > > -    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
> > > +    if (g_hash_table_contains(s->fids, GINT_TO_POINTER(fid))) {
> > > 
> > >          /* If fid is already there return NULL */
> > > 
> > > -        BUG_ON(f->clunked);
> > > -        if (f->fid == fid) {
> > > -            return NULL;
> > > -        }
> > > +        return NULL;
> > 
> > Probably retaining BUG_ON(f->clunked) here?
> 
> I decided not to since this was a sanity check that was happening for
> _each_ fid, but only up to the one we were looking for. This seemed
> inconsistent and awkward to me, so I dropped it completely (and the
> invariant that no clunked fids remain in the table still seems to hold
> -- it's fairly trivial to check, in that the clunked flag is only set
> in two places, both of which also remove the map entry). My preference
> would be to leave it out, but I'd also be fine with restoring it for
> just the one we're looking for, or maybe moving the check to when we're
> iterating over the whole table, e.g. in v9fs_reclaim_fd. Thoughts?

Yeah, I think you are right, it would feel odd. Just drop BUG_ON() for now.

> > > @@ -424,12 +419,11 @@ static V9fsFidState *clunk_fid(V9fsState *s,
> > > int32_t
> > > fid) {
> > > 
> > >      V9fsFidState *fidp;
> > > 
> > > -    QSIMPLEQ_FOREACH(fidp, &s->fid_list, next) {
> > > -        if (fidp->fid == fid) {
> > > -            QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
> > > -            fidp->clunked = true;
> > > -            return fidp;
> > > -        }
> > > +    fidp = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
> > > +    if (fidp) {
> > > +        g_hash_table_remove(s->fids, GINT_TO_POINTER(fid));
> > > +        fidp->clunked = true;
> > > +        return fidp;
> > 
> > We can't get rid of the double lookup here, can we? Surprisingly I don't
> > find a lookup function on the iterator based API.
> 
> It seems you're not the only one who had that idea:
> https://gitlab.gnome.org/GNOME/glib/-/issues/613
> 
> In this case, I think an extended remove function which returns the
> values that were present would be even nicer. But neither exists at this
> time (and that issue is pretty old), I guess we're stuck with this for
> now.

Well, all we would need was such a proposed 
g_hash_table_lookup_iter(table,key,iter) function. I just had a quick look at 
ghash.c and it looks like that would actually be straightforward to add as the 
iterator structure takes the same direct array index as the already existing 
g_hash_table_lookup() function. But anyway, that's the current situation, so 
be it.

> Daniel P. Berrangé writes:
> > In $SUBJECT it is called GHashTable, not GHashMap
> 
> Indeed, good catch. Will fix in the next version.
> 
> Linus

Re: [PATCH] 9pfs: use GHashMap for fid table

[Greg Kurz]

Hi Linus,

Thanks for this promising change !

On Mon, 05 Sep 2022 10:51:10 +0200
Linus Heckemann <git@sphalerite.org> wrote:

> Hi all, thanks for your reviews.
> 
> > @@ -4226,7 +4232,7 @@ int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t,
> >      s->ctx.fmode = fse->fmode;
> >      s->ctx.dmode = fse->dmode;
> > 
> > -    QSIMPLEQ_INIT(&s->fid_list);
> > +    s->fids = g_hash_table_new(NULL, NULL);
> >      qemu_co_rwlock_init(&s->rename_lock);
> > 
> >      if (s->ops->init(&s->ctx, errp) < 0) {
> 
> I noticed that the hash table may be leaked as is. I'll address this in
> the next submission.
> 

Pay attention that this rollback should be added to
v9fs_device_unrealize_common() which is assumed to be
idempotent and is already called on the error path of
v9fs_device_realize_common().

> 
> Philippe Mathieu-Daudé <f4bug@amsat.org> writes:
> > [Style nitpicking]
> 
> Applied these changes and will include them in the next version of the patch.
> 
> Christian Schoenebeck <qemu_oss@crudebyte.com> writes:
> > > @@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t
> > > fid) {
> > >      V9fsFidState *f;
> > > 
> > > -    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
> > > +    if (g_hash_table_contains(s->fids, GINT_TO_POINTER(fid))) {
> > >          /* If fid is already there return NULL */
> > > -        BUG_ON(f->clunked);
> > > -        if (f->fid == fid) {
> > > -            return NULL;
> > > -        }
> > > +        return NULL;
> >
> > Probably retaining BUG_ON(f->clunked) here?
> 
> I decided not to since this was a sanity check that was happening for
> _each_ fid, but only up to the one we were looking for. This seemed
> inconsistent and awkward to me, so I dropped it completely (and the
> invariant that no clunked fids remain in the table still seems to hold
> -- it's fairly trivial to check, in that the clunked flag is only set
> in two places, both of which also remove the map entry). My preference
> would be to leave it out, but I'd also be fine with restoring it for
> just the one we're looking for, or maybe moving the check to when we're
> iterating over the whole table, e.g. in v9fs_reclaim_fd. Thoughts?
> 

Well... finding at least one clunked fid state in this table is
definitely a bug so I'll keep the BUG_ON() anyway.

> > > @@ -424,12 +419,11 @@ static V9fsFidState *clunk_fid(V9fsState *s, int32_t
> > > fid) {
> > >      V9fsFidState *fidp;
> > > 
> > > -    QSIMPLEQ_FOREACH(fidp, &s->fid_list, next) {
> > > -        if (fidp->fid == fid) {
> > > -            QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
> > > -            fidp->clunked = true;
> > > -            return fidp;
> > > -        }
> > > +    fidp = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
> > > +    if (fidp) {
> > > +        g_hash_table_remove(s->fids, GINT_TO_POINTER(fid));
> > > +        fidp->clunked = true;
> > > +        return fidp;
> >
> > We can't get rid of the double lookup here, can we? Surprisingly I don't find 
> > a lookup function on the iterator based API.
> 
> It seems you're not the only one who had that idea:
> https://gitlab.gnome.org/GNOME/glib/-/issues/613
> 
> In this case, I think an extended remove function which returns the
> values that were present would be even nicer. But neither exists at this
> time (and that issue is pretty old), I guess we're stuck with this for
> now.

g_hash_table_steal_extended() [1] actually allows to do just that. Since the
hash table is allocated with g_hash_table_new() and doesn't care for destroy
functions, the code change would be something like:

@@ -424,12 +419,10 @@ static V9fsFidState *clunk_fid(V9fsState *s, int32_t fid)
 {
     V9fsFidState *fidp;
 
-    QSIMPLEQ_FOREACH(fidp, &s->fid_list, next) {
-        if (fidp->fid == fid) {
-            QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
-            fidp->clunked = true;
-            return fidp;
-        }
+    if (g_hash_table_steal_extended(s->fids, GINT_TO_POINTER(fid), NULL,
+                                    (gpointer *)&fidp)) {
+        fidp->clunked = true;
+        return fidp;
     }
     return NULL;
 }

[1] https://developer-old.gnome.org/glib/stable/glib-Hash-Tables.html#g-hash-table-steal-extended

Cheers,

--
Greg

> 
> 
> Daniel P. Berrangé writes:
> > In $SUBJECT it is called GHashTable, not GHashMap
> 
> Indeed, good catch. Will fix in the next version.
> 
> Linus

[PATCH] 9pfs: use GHashTable for fid table

[Linus Heckemann]

The previous implementation would iterate over the fid table for
lookup operations, resulting in an operation with O(n) complexity on
the number of open files and poor cache locality -- for every open,
stat, read, write, etc operation.

This change uses a hashtable for this instead, significantly improving
the performance of the 9p filesystem. The runtime of NixOS's simple
installer test, which copies ~122k files totalling ~1.8GiB from 9p,
decreased by a factor of about 10.

Signed-off-by: Linus Heckemann <git@sphalerite.org>
---
 hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------
 hw/9pfs/9p.h |   2 +-
 2 files changed, 69 insertions(+), 63 deletions(-)

diff --git a/hw/9pfs/9p.c b/hw/9pfs/9p.c
index aebadeaa03..fb4b7fe852 100644
--- a/hw/9pfs/9p.c
+++ b/hw/9pfs/9p.c
@@ -282,33 +282,31 @@ static V9fsFidState *coroutine_fn get_fid(V9fsPDU *pdu, int32_t fid)
     V9fsFidState *f;
     V9fsState *s = pdu->s;
 
-    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
-        BUG_ON(f->clunked);
-        if (f->fid == fid) {
-            /*
-             * Update the fid ref upfront so that
-             * we don't get reclaimed when we yield
-             * in open later.
-             */
-            f->ref++;
-            /*
-             * check whether we need to reopen the
-             * file. We might have closed the fd
-             * while trying to free up some file
-             * descriptors.
-             */
-            err = v9fs_reopen_fid(pdu, f);
-            if (err < 0) {
-                f->ref--;
-                return NULL;
-            }
-            /*
-             * Mark the fid as referenced so that the LRU
-             * reclaim won't close the file descriptor
-             */
-            f->flags |= FID_REFERENCED;
-            return f;
+    f = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
+    if (f) {
+        /*
+         * Update the fid ref upfront so that
+         * we don't get reclaimed when we yield
+         * in open later.
+         */
+        f->ref++;
+        /*
+         * check whether we need to reopen the
+         * file. We might have closed the fd
+         * while trying to free up some file
+         * descriptors.
+         */
+        err = v9fs_reopen_fid(pdu, f);
+        if (err < 0) {
+            f->ref--;
+            return NULL;
         }
+        /*
+         * Mark the fid as referenced so that the LRU
+         * reclaim won't close the file descriptor
+         */
+        f->flags |= FID_REFERENCED;
+        return f;
     }
     return NULL;
 }
@@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid)
 {
     V9fsFidState *f;
 
-    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
+    if (g_hash_table_contains(s->fids, GINT_TO_POINTER(fid))) {
         /* If fid is already there return NULL */
-        BUG_ON(f->clunked);
-        if (f->fid == fid) {
-            return NULL;
-        }
+        return NULL;
     }
     f = g_new0(V9fsFidState, 1);
     f->fid = fid;
@@ -333,7 +328,7 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid)
      * reclaim won't close the file descriptor
      */
     f->flags |= FID_REFERENCED;
-    QSIMPLEQ_INSERT_TAIL(&s->fid_list, f, next);
+    g_hash_table_insert(s->fids, GINT_TO_POINTER(fid), f);
 
     v9fs_readdir_init(s->proto_version, &f->fs.dir);
     v9fs_readdir_init(s->proto_version, &f->fs_reclaim.dir);
@@ -424,12 +419,10 @@ static V9fsFidState *clunk_fid(V9fsState *s, int32_t fid)
 {
     V9fsFidState *fidp;
 
-    QSIMPLEQ_FOREACH(fidp, &s->fid_list, next) {
-        if (fidp->fid == fid) {
-            QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
-            fidp->clunked = true;
-            return fidp;
-        }
+    if (g_hash_table_steal_extended(s->fids, GINT_TO_POINTER(fid),
+                                    NULL, (gpointer *) &fidp)) {
+        fidp->clunked = true;
+        return fidp;
     }
     return NULL;
 }
@@ -439,10 +432,15 @@ void coroutine_fn v9fs_reclaim_fd(V9fsPDU *pdu)
     int reclaim_count = 0;
     V9fsState *s = pdu->s;
     V9fsFidState *f;
+    GHashTableIter iter;
+    gpointer fid;
+
+    g_hash_table_iter_init(&iter, s->fids);
+
     QSLIST_HEAD(, V9fsFidState) reclaim_list =
         QSLIST_HEAD_INITIALIZER(reclaim_list);
 
-    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
+    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &f)) {
         /*
          * Unlink fids cannot be reclaimed. Check
          * for them and skip them. Also skip fids
@@ -518,12 +516,11 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
 {
     int err;
     V9fsState *s = pdu->s;
-    V9fsFidState *fidp, *fidp_next;
+    V9fsFidState *fidp;
+    gpointer fid;
+    GHashTableIter iter;
 
-    fidp = QSIMPLEQ_FIRST(&s->fid_list);
-    if (!fidp) {
-        return 0;
-    }
+    g_hash_table_iter_init(&iter, s->fids);
 
     /*
      * v9fs_reopen_fid() can yield : a reference on the fid must be held
@@ -534,7 +531,13 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
      * iteration after we could get a reference on the next fid. Start with
      * the first one.
      */
-    for (fidp->ref++; fidp; fidp = fidp_next) {
+    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &fidp)) {
+        /*
+         * Ensure the fid survives a potential clunk request during
+         * put_fid() below and v9fs_reopen_fid() in the next iteration.
+         */
+        fidp->ref++;
+
         if (fidp->path.size == path->size &&
             !memcmp(fidp->path.data, path->data, path->size)) {
             /* Mark the fid non reclaimable. */
@@ -548,16 +551,6 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
             }
         }
 
-        fidp_next = QSIMPLEQ_NEXT(fidp, next);
-
-        if (fidp_next) {
-            /*
-             * Ensure the next fid survives a potential clunk request during
-             * put_fid() below and v9fs_reopen_fid() in the next iteration.
-             */
-            fidp_next->ref++;
-        }
-
         /* We're done with this fid */
         put_fid(pdu, fidp);
     }
@@ -569,19 +562,21 @@ static void coroutine_fn virtfs_reset(V9fsPDU *pdu)
 {
     V9fsState *s = pdu->s;
     V9fsFidState *fidp;
+    gpointer fid;
+    GHashTableIter iter;
+
+    g_hash_table_iter_init(&iter, s->fids);
 
     /* Free all fids */
-    while (!QSIMPLEQ_EMPTY(&s->fid_list)) {
-        /* Get fid */
-        fidp = QSIMPLEQ_FIRST(&s->fid_list);
+    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &fidp)) {
         fidp->ref++;
 
         /* Clunk fid */
-        QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
         fidp->clunked = true;
 
         put_fid(pdu, fidp);
     }
+    g_hash_table_remove_all(s->fids);
 }
 
 #define P9_QID_TYPE_DIR         0x80
@@ -3205,6 +3200,8 @@ static int coroutine_fn v9fs_complete_rename(V9fsPDU *pdu, V9fsFidState *fidp,
     V9fsFidState *tfidp;
     V9fsState *s = pdu->s;
     V9fsFidState *dirfidp = NULL;
+    GHashTableIter iter;
+    gpointer fid;
 
     v9fs_path_init(&new_path);
     if (newdirfid != -1) {
@@ -3238,11 +3235,13 @@ static int coroutine_fn v9fs_complete_rename(V9fsPDU *pdu, V9fsFidState *fidp,
     if (err < 0) {
         goto out;
     }
+
     /*
      * Fixup fid's pointing to the old name to
      * start pointing to the new name
      */
-    QSIMPLEQ_FOREACH(tfidp, &s->fid_list, next) {
+    g_hash_table_iter_init(&iter, s->fids);
+    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &tfidp)) {
         if (v9fs_path_is_ancestor(&fidp->path, &tfidp->path)) {
             /* replace the name */
             v9fs_fix_path(&tfidp->path, &new_path, strlen(fidp->path.data));
@@ -3320,6 +3319,8 @@ static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir,
     V9fsPath oldpath, newpath;
     V9fsState *s = pdu->s;
     int err;
+    GHashTableIter iter;
+    gpointer fid;
 
     v9fs_path_init(&oldpath);
     v9fs_path_init(&newpath);
@@ -3336,7 +3337,8 @@ static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir,
      * Fixup fid's pointing to the old name to
      * start pointing to the new name
      */
-    QSIMPLEQ_FOREACH(tfidp, &s->fid_list, next) {
+    g_hash_table_iter_init(&iter, s->fids);
+    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &tfidp)) {
         if (v9fs_path_is_ancestor(&oldpath, &tfidp->path)) {
             /* replace the name */
             v9fs_fix_path(&tfidp->path, &newpath, strlen(oldpath.data));
@@ -4226,7 +4228,7 @@ int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t,
     s->ctx.fmode = fse->fmode;
     s->ctx.dmode = fse->dmode;
 
-    QSIMPLEQ_INIT(&s->fid_list);
+    s->fids = g_hash_table_new(NULL, NULL);
     qemu_co_rwlock_init(&s->rename_lock);
 
     if (s->ops->init(&s->ctx, errp) < 0) {
@@ -4286,6 +4288,10 @@ void v9fs_device_unrealize_common(V9fsState *s)
     if (s->ctx.fst) {
         fsdev_throttle_cleanup(s->ctx.fst);
     }
+    if (s->fids) {
+        g_hash_table_destroy(s->fids);
+        s->fids = NULL;
+    }
     g_free(s->tag);
     qp_table_destroy(&s->qpd_table);
     qp_table_destroy(&s->qpp_table);
diff --git a/hw/9pfs/9p.h b/hw/9pfs/9p.h
index 994f952600..10fd2076c2 100644
--- a/hw/9pfs/9p.h
+++ b/hw/9pfs/9p.h
@@ -339,7 +339,7 @@ typedef struct {
 struct V9fsState {
     QLIST_HEAD(, V9fsPDU) free_list;
     QLIST_HEAD(, V9fsPDU) active_list;
-    QSIMPLEQ_HEAD(, V9fsFidState) fid_list;
+    GHashTable *fids;
     FileOperations *ops;
     FsContext ctx;
     char *tag;
-- 
2.36.0

Re: [PATCH v2] 9pfs: use GHashTable for fid table

[Philippe Mathieu-Daudé via]

On 5/9/22 17:03, Linus Heckemann wrote:
> The previous implementation would iterate over the fid table for
> lookup operations, resulting in an operation with O(n) complexity on
> the number of open files and poor cache locality -- for every open,
> stat, read, write, etc operation.
> 
> This change uses a hashtable for this instead, significantly improving
> the performance of the 9p filesystem. The runtime of NixOS's simple
> installer test, which copies ~122k files totalling ~1.8GiB from 9p,
> decreased by a factor of about 10.
> 
> Signed-off-by: Linus Heckemann <git@sphalerite.org>
> ---
>   hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------
>   hw/9pfs/9p.h |   2 +-
>   2 files changed, 69 insertions(+), 63 deletions(-)

Watch out to iterate the version when respining patches:

"Send each new revision as a new top-level thread, rather than burying 
it in-reply-to an earlier revision, as many reviewers are not looking 
inside deep threads for new patches."
https://www.qemu.org/docs/master/devel/submitting-a-patch.html#when-resending-patches-add-a-version-tag
Reviewed-by: Philippe Mathieu-Daudé <f4bug@amsat.org>

Re: [PATCH] 9pfs: use GHashTable for fid table

[Greg Kurz]

Hi Linus,

Some more comments below.

On Mon,  5 Sep 2022 17:03:00 +0200
Linus Heckemann <git@sphalerite.org> wrote:

> The previous implementation would iterate over the fid table for
> lookup operations, resulting in an operation with O(n) complexity on
> the number of open files and poor cache locality -- for every open,
> stat, read, write, etc operation.
> 
> This change uses a hashtable for this instead, significantly improving
> the performance of the 9p filesystem. The runtime of NixOS's simple
> installer test, which copies ~122k files totalling ~1.8GiB from 9p,
> decreased by a factor of about 10.
> 
> Signed-off-by: Linus Heckemann <git@sphalerite.org>
> ---
>  hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------
>  hw/9pfs/9p.h |   2 +-
>  2 files changed, 69 insertions(+), 63 deletions(-)
> 
> diff --git a/hw/9pfs/9p.c b/hw/9pfs/9p.c
> index aebadeaa03..fb4b7fe852 100644
> --- a/hw/9pfs/9p.c
> +++ b/hw/9pfs/9p.c
> @@ -282,33 +282,31 @@ static V9fsFidState *coroutine_fn get_fid(V9fsPDU *pdu, int32_t fid)
>      V9fsFidState *f;
>      V9fsState *s = pdu->s;
>  
> -    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
> -        BUG_ON(f->clunked);
> -        if (f->fid == fid) {
> -            /*
> -             * Update the fid ref upfront so that
> -             * we don't get reclaimed when we yield
> -             * in open later.
> -             */
> -            f->ref++;
> -            /*
> -             * check whether we need to reopen the
> -             * file. We might have closed the fd
> -             * while trying to free up some file
> -             * descriptors.
> -             */
> -            err = v9fs_reopen_fid(pdu, f);
> -            if (err < 0) {
> -                f->ref--;
> -                return NULL;
> -            }
> -            /*
> -             * Mark the fid as referenced so that the LRU
> -             * reclaim won't close the file descriptor
> -             */
> -            f->flags |= FID_REFERENCED;
> -            return f;
> +    f = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
> +    if (f) {
> +        /*
> +         * Update the fid ref upfront so that
> +         * we don't get reclaimed when we yield
> +         * in open later.
> +         */
> +        f->ref++;
> +        /*
> +         * check whether we need to reopen the
> +         * file. We might have closed the fd
> +         * while trying to free up some file
> +         * descriptors.
> +         */
> +        err = v9fs_reopen_fid(pdu, f);
> +        if (err < 0) {
> +            f->ref--;
> +            return NULL;
>          }
> +        /*
> +         * Mark the fid as referenced so that the LRU
> +         * reclaim won't close the file descriptor
> +         */
> +        f->flags |= FID_REFERENCED;
> +        return f;
>      }
>      return NULL;
>  }
> @@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid)
>  {
>      V9fsFidState *f;
>  
> -    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
> +    if (g_hash_table_contains(s->fids, GINT_TO_POINTER(fid))) {
>          /* If fid is already there return NULL */
> -        BUG_ON(f->clunked);
> -        if (f->fid == fid) {
> -            return NULL;
> -        }
> +        return NULL;
>      }
>      f = g_new0(V9fsFidState, 1);
>      f->fid = fid;
> @@ -333,7 +328,7 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid)
>       * reclaim won't close the file descriptor
>       */
>      f->flags |= FID_REFERENCED;
> -    QSIMPLEQ_INSERT_TAIL(&s->fid_list, f, next);
> +    g_hash_table_insert(s->fids, GINT_TO_POINTER(fid), f);
>  
>      v9fs_readdir_init(s->proto_version, &f->fs.dir);
>      v9fs_readdir_init(s->proto_version, &f->fs_reclaim.dir);
> @@ -424,12 +419,10 @@ static V9fsFidState *clunk_fid(V9fsState *s, int32_t fid)
>  {
>      V9fsFidState *fidp;
>  
> -    QSIMPLEQ_FOREACH(fidp, &s->fid_list, next) {
> -        if (fidp->fid == fid) {
> -            QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
> -            fidp->clunked = true;
> -            return fidp;
> -        }
> +    if (g_hash_table_steal_extended(s->fids, GINT_TO_POINTER(fid),
> +                                    NULL, (gpointer *) &fidp)) {
> +        fidp->clunked = true;
> +        return fidp;
>      }
>      return NULL;
>  }
> @@ -439,10 +432,15 @@ void coroutine_fn v9fs_reclaim_fd(V9fsPDU *pdu)
>      int reclaim_count = 0;
>      V9fsState *s = pdu->s;
>      V9fsFidState *f;
> +    GHashTableIter iter;
> +    gpointer fid;
> +
> +    g_hash_table_iter_init(&iter, s->fids);
> +
>      QSLIST_HEAD(, V9fsFidState) reclaim_list =
>          QSLIST_HEAD_INITIALIZER(reclaim_list);
>  
> -    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
> +    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &f)) {
>          /*
>           * Unlink fids cannot be reclaimed. Check
>           * for them and skip them. Also skip fids
> @@ -518,12 +516,11 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
>  {
>      int err;
>      V9fsState *s = pdu->s;
> -    V9fsFidState *fidp, *fidp_next;
> +    V9fsFidState *fidp;
> +    gpointer fid;
> +    GHashTableIter iter;
>  
> -    fidp = QSIMPLEQ_FIRST(&s->fid_list);
> -    if (!fidp) {
> -        return 0;
> -    }
> +    g_hash_table_iter_init(&iter, s->fids);
>  

Using this external iterator API instead of the embedded QSIMPLEQ entry
definitely simplifies logic. Thanks !

>      /*
>       * v9fs_reopen_fid() can yield : a reference on the fid must be held
> @@ -534,7 +531,13 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
>       * iteration after we could get a reference on the next fid. Start with
>       * the first one.
>       */

The comment above should be adapted to the new situation : no need
to do anything special with the next fid since we're not getting
a pointer to it before calling the "We're done with this fid" put_fid()
on the current fid.

> -    for (fidp->ref++; fidp; fidp = fidp_next) {
> +    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &fidp)) {
> +        /*
> +         * Ensure the fid survives a potential clunk request during
> +         * put_fid() below and v9fs_reopen_fid() in the next iteration.

With the new logic, this should just be:

Ensure the fid survives a potential clunk request during v9fs_reopen_fid().

> +         */
> +        fidp->ref++;
> +
>          if (fidp->path.size == path->size &&
>              !memcmp(fidp->path.data, path->data, path->size)) {
>              /* Mark the fid non reclaimable. */
> @@ -548,16 +551,6 @@ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
>              }
>          }
>  
> -        fidp_next = QSIMPLEQ_NEXT(fidp, next);
> -
> -        if (fidp_next) {
> -            /*
> -             * Ensure the next fid survives a potential clunk request during
> -             * put_fid() below and v9fs_reopen_fid() in the next iteration.
> -             */
> -            fidp_next->ref++;
> -        }
> -
>          /* We're done with this fid */
>          put_fid(pdu, fidp);
>      }
> @@ -569,19 +562,21 @@ static void coroutine_fn virtfs_reset(V9fsPDU *pdu)
>  {
>      V9fsState *s = pdu->s;
>      V9fsFidState *fidp;
> +    gpointer fid;
> +    GHashTableIter iter;
> +
> +    g_hash_table_iter_init(&iter, s->fids);
>  
>      /* Free all fids */
> -    while (!QSIMPLEQ_EMPTY(&s->fid_list)) {
> -        /* Get fid */
> -        fidp = QSIMPLEQ_FIRST(&s->fid_list);
> +    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &fidp)) {
>          fidp->ref++;
>  
>          /* Clunk fid */
> -        QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);

You could just call g_hash_table_iter_remove(&iter) here (it is
safe according to the glib documentation [1]) and...

>          fidp->clunked = true;
>  
>          put_fid(pdu, fidp);
>      }
> +    g_hash_table_remove_all(s->fids);

... avoid the extra loop, but no big deal.

Rest looks ok. Please re-post and add:

Reviewed-by: Greg Kurz <groug@kaod.org>

Don't forget to put a v3 in the subject and provide the list of changes
since v2 below the '---' terminator of the commit message (see [2] for
an example). You might want to try out 'git publish' [3], a marvelous
tool that helps a lot with the tedious process of posting versionned
patch series.

Cheers,

--
Greg

[1] https://developer-old.gnome.org/glib/stable/glib-Hash-Tables.html#g-hash-table-iter-remove
[2] https://patchwork.ozlabs.org/project/qemu-devel/patch/20210121181510.1459390-1-groug@kaod.org/
[3] https://github.com/stefanha/git-publish

>  }
>  
>  #define P9_QID_TYPE_DIR         0x80
> @@ -3205,6 +3200,8 @@ static int coroutine_fn v9fs_complete_rename(V9fsPDU *pdu, V9fsFidState *fidp,
>      V9fsFidState *tfidp;
>      V9fsState *s = pdu->s;
>      V9fsFidState *dirfidp = NULL;
> +    GHashTableIter iter;
> +    gpointer fid;
>  
>      v9fs_path_init(&new_path);
>      if (newdirfid != -1) {
> @@ -3238,11 +3235,13 @@ static int coroutine_fn v9fs_complete_rename(V9fsPDU *pdu, V9fsFidState *fidp,
>      if (err < 0) {
>          goto out;
>      }
> +
>      /*
>       * Fixup fid's pointing to the old name to
>       * start pointing to the new name
>       */
> -    QSIMPLEQ_FOREACH(tfidp, &s->fid_list, next) {
> +    g_hash_table_iter_init(&iter, s->fids);
> +    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &tfidp)) {
>          if (v9fs_path_is_ancestor(&fidp->path, &tfidp->path)) {
>              /* replace the name */
>              v9fs_fix_path(&tfidp->path, &new_path, strlen(fidp->path.data));
> @@ -3320,6 +3319,8 @@ static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir,
>      V9fsPath oldpath, newpath;
>      V9fsState *s = pdu->s;
>      int err;
> +    GHashTableIter iter;
> +    gpointer fid;
>  
>      v9fs_path_init(&oldpath);
>      v9fs_path_init(&newpath);
> @@ -3336,7 +3337,8 @@ static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir,
>       * Fixup fid's pointing to the old name to
>       * start pointing to the new name
>       */
> -    QSIMPLEQ_FOREACH(tfidp, &s->fid_list, next) {
> +    g_hash_table_iter_init(&iter, s->fids);
> +    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &tfidp)) {
>          if (v9fs_path_is_ancestor(&oldpath, &tfidp->path)) {
>              /* replace the name */
>              v9fs_fix_path(&tfidp->path, &newpath, strlen(oldpath.data));
> @@ -4226,7 +4228,7 @@ int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t,
>      s->ctx.fmode = fse->fmode;
>      s->ctx.dmode = fse->dmode;
>  
> -    QSIMPLEQ_INIT(&s->fid_list);
> +    s->fids = g_hash_table_new(NULL, NULL);
>      qemu_co_rwlock_init(&s->rename_lock);
>  
>      if (s->ops->init(&s->ctx, errp) < 0) {
> @@ -4286,6 +4288,10 @@ void v9fs_device_unrealize_common(V9fsState *s)
>      if (s->ctx.fst) {
>          fsdev_throttle_cleanup(s->ctx.fst);
>      }
> +    if (s->fids) {
> +        g_hash_table_destroy(s->fids);
> +        s->fids = NULL;
> +    }
>      g_free(s->tag);
>      qp_table_destroy(&s->qpd_table);
>      qp_table_destroy(&s->qpp_table);
> diff --git a/hw/9pfs/9p.h b/hw/9pfs/9p.h
> index 994f952600..10fd2076c2 100644
> --- a/hw/9pfs/9p.h
> +++ b/hw/9pfs/9p.h
> @@ -339,7 +339,7 @@ typedef struct {
>  struct V9fsState {
>      QLIST_HEAD(, V9fsPDU) free_list;
>      QLIST_HEAD(, V9fsPDU) active_list;
> -    QSIMPLEQ_HEAD(, V9fsFidState) fid_list;
> +    GHashTable *fids;
>      FileOperations *ops;
>      FsContext ctx;
>      char *tag;