Merge pull request #195830 from DeterminateSystems/qemu-9p-patch

qemu: add patch improving 9p performance

2 files changed, 372 insertions, 0 deletions

diff --git a/pkgs/applications/virtualization/qemu/9pfs-use-GHashTable-for-fid-table.patch b/pkgs/applications/virtualization/qemu/9pfs-use-GHashTable-for-fid-table.patch
new file mode 100644
index 0000000000000..2e6f1699637b1
--- /dev/null
+++ b/pkgs/applications/virtualization/qemu/9pfs-use-GHashTable-for-fid-table.patch
@@ -0,0 +1,371 @@
+From 8ab70b8958a8f9cb9bd316eecd3ccbcf05c06614 Mon Sep 17 00:00:00 2001
+From: Linus Heckemann <git@sphalerite.org>
+Date: Tue, 4 Oct 2022 12:41:21 +0200
+Subject: [PATCH] 9pfs: use GHashTable for fid table
+MIME-Version: 1.0
+Content-Type: text/plain; charset=UTF-8
+Content-Transfer-Encoding: 8bit
+
+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>
+Reviewed-by: Philippe Mathieu-Daudé <f4bug@amsat.org>
+Reviewed-by: Greg Kurz <groug@kaod.org>
+[CS: - Retain BUG_ON(f->clunked) in get_fid().
+     - Add TODO comment in clunk_fid(). ]
+Message-Id: <20221004104121.713689-1-git@sphalerite.org>
+[CS: - Drop unnecessary goto and out: label. ]
+Signed-off-by: Christian Schoenebeck <qemu_oss@crudebyte.com>
+---
+ hw/9pfs/9p.c | 194 +++++++++++++++++++++++++++++----------------------
+ hw/9pfs/9p.h |   2 +-
+ 2 files changed, 112 insertions(+), 84 deletions(-)
+
+diff --git a/hw/9pfs/9p.c b/hw/9pfs/9p.c
+index aebadeaa03..9bf13133e5 100644
+--- a/hw/9pfs/9p.c
++++ b/hw/9pfs/9p.c
+@@ -256,7 +256,8 @@ static size_t v9fs_string_size(V9fsString *str)
+ }
+ 
+ /*
+- * returns 0 if fid got re-opened, 1 if not, < 0 on error */
++ * returns 0 if fid got re-opened, 1 if not, < 0 on error
++ */
+ static int coroutine_fn v9fs_reopen_fid(V9fsPDU *pdu, V9fsFidState *f)
+ {
+     int err = 1;
+@@ -282,33 +283,32 @@ static V9fsFidState *coroutine_fn get_fid(V9fsPDU *pdu, int32_t fid)
+     V9fsFidState *f;
+     V9fsState *s = pdu->s;
+ 
+-    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
++    f = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
++    if (f) {
+         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;
++        /*
++         * 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 +317,11 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid)
+ {
+     V9fsFidState *f;
+ 
+-    QSIMPLEQ_FOREACH(f, &s->fid_list, next) {
++    f = g_hash_table_lookup(s->fids, GINT_TO_POINTER(fid));
++    if (f) {
+         /* 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 +332,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 +423,12 @@ 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;
+-        }
++    /* TODO: Use g_hash_table_steal_extended() instead? */
++    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 +438,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
+@@ -514,72 +518,85 @@ void coroutine_fn v9fs_reclaim_fd(V9fsPDU *pdu)
+     }
+ }
+ 
++/*
++ * This is used when a path is removed from the directory tree. Any
++ * fids that still reference it must not be closed from then on, since
++ * they cannot be reopened.
++ */
+ static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path)
+ {
+-    int err;
++    int err = 0;
+     V9fsState *s = pdu->s;
+-    V9fsFidState *fidp, *fidp_next;
++    V9fsFidState *fidp;
++    gpointer fid;
++    GHashTableIter iter;
++    /*
++     * The most common case is probably that we have exactly one
++     * fid for the given path, so preallocate exactly one.
++     */
++    g_autoptr(GArray) to_reopen = g_array_sized_new(FALSE, FALSE,
++            sizeof(V9fsFidState *), 1);
++    gint i;
+ 
+-    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
+-     * to ensure its pointer remains valid and we can safely pass it to
+-     * QSIMPLEQ_NEXT(). The corresponding put_fid() can also yield so
+-     * we must keep a reference on the next fid as well. So the logic here
+-     * is to get a reference on a fid and only put it back during the next
+-     * iteration after we could get a reference on the next fid. Start with
+-     * the first one.
++     * We iterate over the fid table looking for the entries we need
++     * to reopen, and store them in to_reopen. This is because
++     * v9fs_reopen_fid() and put_fid() yield. This allows the fid table
++     * to be modified in the meantime, invalidating our iterator.
+      */
+-    for (fidp->ref++; fidp; fidp = fidp_next) {
++    while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &fidp)) {
+         if (fidp->path.size == path->size &&
+             !memcmp(fidp->path.data, path->data, path->size)) {
+-            /* Mark the fid non reclaimable. */
+-            fidp->flags |= FID_NON_RECLAIMABLE;
+-
+-            /* reopen the file/dir if already closed */
+-            err = v9fs_reopen_fid(pdu, fidp);
+-            if (err < 0) {
+-                put_fid(pdu, fidp);
+-                return err;
+-            }
+-        }
+-
+-        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.
++             * Ensure the fid survives a potential clunk request during
++             * v9fs_reopen_fid or put_fid.
+              */
+-            fidp_next->ref++;
++            fidp->ref++;
++            fidp->flags |= FID_NON_RECLAIMABLE;
++            g_array_append_val(to_reopen, fidp);
+         }
++    }
+ 
+-        /* We're done with this fid */
+-        put_fid(pdu, fidp);
++    for (i = 0; i < to_reopen->len; i++) {
++        fidp = g_array_index(to_reopen, V9fsFidState*, i);
++        /* reopen the file/dir if already closed */
++        err = v9fs_reopen_fid(pdu, fidp);
++        if (err < 0) {
++            break;
++        }
+     }
+ 
+-    return 0;
++    for (i = 0; i < to_reopen->len; i++) {
++        put_fid(pdu, g_array_index(to_reopen, V9fsFidState*, i));
++    }
++    return err;
+ }
+ 
+ static void coroutine_fn virtfs_reset(V9fsPDU *pdu)
+ {
+     V9fsState *s = pdu->s;
+     V9fsFidState *fidp;
++    GList *freeing;
++    /*
++     * Get a list of all the values (fid states) in the table, which
++     * we then...
++     */
++    g_autoptr(GList) fids = g_hash_table_get_values(s->fids);
+ 
+-    /* Free all fids */
+-    while (!QSIMPLEQ_EMPTY(&s->fid_list)) {
+-        /* Get fid */
+-        fidp = QSIMPLEQ_FIRST(&s->fid_list);
+-        fidp->ref++;
++    /* ... remove from the table, taking over ownership. */
++    g_hash_table_steal_all(s->fids);
+ 
+-        /* Clunk fid */
+-        QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next);
++    /*
++     * This allows us to release our references to them asynchronously without
++     * iterating over the hash table and risking iterator invalidation
++     * through concurrent modifications.
++     */
++    for (freeing = fids; freeing; freeing = freeing->next) {
++        fidp = freeing->data;
++        fidp->ref++;
+         fidp->clunked = true;
+-
+         put_fid(pdu, fidp);
+     }
+ }
+@@ -3205,6 +3222,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 +3257,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 +3341,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 +3359,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 +4250,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 +4310,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.2
+
diff --git a/pkgs/applications/virtualization/qemu/default.nix b/pkgs/applications/virtualization/qemu/default.nix
index 4f55b48bc540c..5873c24f15a24 100644
--- a/pkgs/applications/virtualization/qemu/default.nix
+++ b/pkgs/applications/virtualization/qemu/default.nix
@@ -111,6 +111,7 @@ stdenv.mkDerivation rec {
       sha256 = "sha256-oC+bRjEHixv1QEFO9XAm4HHOwoiT+NkhknKGPydnZ5E=";
       revert = true;
     })
+    ./9pfs-use-GHashTable-for-fid-table.patch
   ]
   ++ lib.optional nixosTestRunner ./force-uid0-on-9p.patch;