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

["Philippe Mathieu-Daudé via" <qemu-devel@nongnu.org>]

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>