9pfs: use GHashMap for fid table
PATCH 1/1 9pfs: use GHashMap for fid table
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.
--- hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------ hw/9pfs/9p.h | 2 +- 2 files changed, 69 insertions(+), 63 deletions(-)
hw/9pfs/9p.c +68 -62
@@ -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 ) {
hw/9pfs/9p.h +1 -1
@@ -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;
Signature · 1 line
2.36.0
Hi Linus,
Quoted 35 lines · 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 <[email protected]>--- hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------ hw/9pfs/9p.h | 2 +- 2 files changed, 69 insertions(+), 63 deletions(-)hw/9pfs/9p.c +5
-6@@ -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 ; }
hw/9pfs/9p.c void coroutine_fn v9fs_reclaim_fd(V9fsPDU *pdu) · line 436
Quoted 4 lines
hw/9pfs/9p.c +1
-0@@ -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 ...
Review void coroutine_fn v9fs_reclaim_fd(V9fsPDU *pdu) · line 438
Quoted 2 lines
(quoted diff) +2
-0+ GHashTableIter iter; + gpointer fid;
... here.
hw/9pfs/9p.c void coroutine_fn v9fs_reclaim_fd(V9fsPDU *pdu) · line 444
Quoted 7 lines
hw/9pfs/9p.c +3
-1+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.
hw/9pfs/9p.c static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path) · line 523
Quoted 12 lines
hw/9pfs/9p.c +4
-1/* * 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.
Quoted 10 lines
hw/9pfs/9p.c +1
-4+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
hw/9pfs/9p.c static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path) · line 536
Quoted 5 lines
hw/9pfs/9p.c +1
-1@@ -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 *.
Quoted 27 lines
hw/9pfs/9p.c +6
-10+/* +* 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); }
hw/9pfs/9p.c static void coroutine_fn virtfs_reset(V9fsPDU *pdu) · line 569
Quoted 5 lines
hw/9pfs/9p.c +2
-0@@ -570,18 +565,20 @@ static void coroutine_fn virtfs_reset(V9fsPDU *pdu)V9fsState *s = pdu->s;V9fsFidState *fidp; +gpointer fid; +GHashTableIter iter;
Style.
hw/9pfs/9p.c static void coroutine_fn virtfs_reset(V9fsPDU *pdu) · line 573
Quoted 7 lines
hw/9pfs/9p.c +3
-3+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 *.
Quoted 13 lines
hw/9pfs/9p.c +1
-1fidp->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
hw/9pfs/9p.c static int coroutine_fn v9fs_complete_rename(V9fsPDU *pdu, V9fsFidState *fidp, · line 3205
Quoted 3 lines
hw/9pfs/9p.c +0
-0@@ -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.
Quoted 22 lines
hw/9pfs/9p.c +6
-1+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));
hw/9pfs/9p.c static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir, · line 3325
Quoted 3 lines
hw/9pfs/9p.c +0
-0@@ -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.
hw/9pfs/9p.c static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir, · line 3345
Quoted 13 lines
hw/9pfs/9p.c +5
-1+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 *.
hw/9pfs/9p.c int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t, · line 4236
Quoted 10 lines
hw/9pfs/9p.c +1
-1if (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:
Hi all, thanks for your reviews.
hw/9pfs/9p.c int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t, · line 4238
Quoted 9 lines
hw/9pfs/9p.c +1
-1@@ -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.
Quoted 1 line · Philippe Mathieu-Daudé
[Style nitpicking]
Applied these changes and will include them in the next version of the patch.
Quoted 4 lines · Christian Schoenebeck
Quoted 4 lines
hw/9pfs/9p.c +0
-0@@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid) {V9fsFidState *f;
Quoted 10 lines
hw/9pfs/9p.c static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid) · line 320
Quoted 8 lines
hw/9pfs/9p.c +2
-5- 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?
Quoted 4 lines
Quoted 4 lines
hw/9pfs/9p.c +0
-0@@ -424,12 +419,11 @@ static V9fsFidState *clunk_fid(V9fsState *s, int32_t fid) {V9fsFidState *fidp;
Quoted 14 lines
hw/9pfs/9p.c static V9fsFidState *clunk_fid(V9fsState *s, int32_t fid) · line 426
Quoted 11 lines
hw/9pfs/9p.c +5
-6- 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.
Quoted 1 line · Daniel P. Berrangé
In $SUBJECT it is called GHashTable, not GHashMap
Indeed, good catch. Will fix in the next version.
Linus
Quoted 42 lines · On Montag, 5. September 2022 10:51:10 CEST Linus Heckemann wrote:
Hi all, thanks for your reviews.
hw/9pfs/9p.c int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t, · line 4238
Quoted 11 lines
(quoted diff) +0
-0@@ -4226,7 +4232,7 @@ int v9fs_device_realize_common(V9fsState *s, constV9fsTransport *t,>
s->ctx.fmode = fse->fmode; s->ctx.dmode = fse->dmode;hw/9pfs/9p.c +1
-1-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.
Quoted 1 line · Philippe Mathieu-Daudé
[Style nitpicking]
Applied these changes and will include them in the next version of the patch.
Quoted 11 lines · Christian Schoenebeck
Quoted 11 lines
(quoted diff) +0
-0@@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s,
int32_t
fid) {V9fsFidState *f;hw/9pfs/9p.c +1
-1- 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 */ Quoted 7 lines
hw/9pfs/9p.c static V9fsFidState *coroutine_fn get_fid(V9fsPDU *pdu, int32_t fid) · line 302
Quoted 5 lines
hw/9pfs/9p.c +1
-4-BUG_ON (f->clunked); -if (f->fid == fid) { -return NULL ; - } +return NULL ;Probably retaining
BUG_ON(f->clunked)here?
Quoted 9 lines
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.
Quoted 21 lines
Quoted 6 lines
Quoted 6 lines
(quoted diff) +0
-0@@ -424,12 +419,11 @@ static V9fsFidState *clunk_fid(V9fsState *s,
int32_t
fid) {V9fsFidState *fidp;Quoted 14 lines
hw/9pfs/9p.c static V9fsFidState *clunk_fid(V9fsState *s, int32_t fid) · line 426
Quoted 11 lines
hw/9pfs/9p.c +5
-6- 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.
Quoted 7 lines
It seems you're not the only one who had that idea:
https://gitlab.gnome.org/GNOME/glib/-/issues/613In 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.
Quoted 6 lines
Quoted 1 line · Daniel P. Berrangé
In $SUBJECT it is called GHashTable, not GHashMap
Indeed, good catch. Will fix in the next version.
Linus
Hi Linus,
Thanks for this promising change !
Quoted 6 lines · On Mon, 05 Sep 2022 10:51:10 +0200 Linus Heckemann <[email protected]> wrote:
Hi all, thanks for your reviews.
Quoted 4 lines
hw/9pfs/9p.c +0
-0@@ -4226,7 +4232,7 @@ int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t, s->ctx.fmode = fse->fmode; s->ctx.dmode = fse->dmode;
Quoted 9 lines
hw/9pfs/9p.c int v9fs_device_realize_common(V9fsState *s, const V9fsTransport *t, · line 4238
Quoted 5 lines
hw/9pfs/9p.c +1
-1-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().
Quoted 22 lines
Quoted 1 line · Philippe Mathieu-Daudé
[Style nitpicking]
Applied these changes and will include them in the next version of the patch.
Quoted 4 lines · Christian Schoenebeck
Quoted 4 lines
hw/9pfs/9p.c +0
-0@@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid) {V9fsFidState *f;Quoted 10 lines
hw/9pfs/9p.c static V9fsFidState *alloc_fid(V9fsState *s, int32_t fid) · line 320
Quoted 8 lines
hw/9pfs/9p.c +2
-5- 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?
Quoted 10 lines
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.
Quoted 19 lines
Quoted 4 lines
Quoted 4 lines
hw/9pfs/9p.c +0
-0@@ -424,12 +419,11 @@ static V9fsFidState *clunk_fid(V9fsState *s, int32_t fid) {V9fsFidState *fidp;Quoted 14 lines
hw/9pfs/9p.c static V9fsFidState *clunk_fid(V9fsState *s, int32_t fid) · line 426
Quoted 11 lines
hw/9pfs/9p.c +5
-6- 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.
Quoted 7 lines
It seems you're not the only one who had that idea:
https://gitlab.gnome.org/GNOME/glib/-/issues/613In 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
Quoted 8 lines
Quoted 1 line · Daniel P. Berrangé
In $SUBJECT it is called GHashTable, not GHashMap
Indeed, good catch. Will fix in the next version.
Linus
Quoted 4 lines · 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!
Quoted 4 lines
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 ...
Quoted 70 lines
Signed-off-by Linus Heckemann <[email protected]>--- hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------ hw/9pfs/9p.h | 2 +- 2 files changed, 69 insertions(+), 63 deletions(-)hw/9pfs/9p.c +24
-26@@ -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) {
hw/9pfs/9p.c static V9fsFidState *alloc_fid(V9fsState *s, int32_t · line 320
Quoted 10 lines
hw/9pfs/9p.c +2
-5V9fsFidState *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?
Quoted 17 lines
hw/9pfs/9p.c +0
-0} f =g_new0 (V9fsFidState,1 ); f->fid = fid;@@ -333,7 +328,7 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_tfid) * reclaim won't close the file descriptor
*/ f->flags |= FID_REFERENCED;hw/9pfs/9p.c +1
-2-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) {
hw/9pfs/9p.c static V9fsFidState *clunk_fid(V9fsState *s, int32_t · line 426
Quoted 10 lines
hw/9pfs/9p.c +5
-5-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.
Quoted 42 lines
hw/9pfs/9p.c +11
-6}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.*/
hw/9pfs/9p.c static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path) · line 536
Quoted 2 lines
hw/9pfs/9p.c +1
-1-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
Quoted 118 lines
hw/9pfs/9p.c +6
-5+/* +* 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 andv9fs_reopen_fid()in the next
iteration. - */hw/9pfs/9p.c +12
-8- 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 intcoroutine_fnv9fs_fix_fid_paths(V9fsPDU *pdu, V9fsPath *olddir, V9fsState *s = pdu->s; int err;hw/9pfs/9p.c +6
-2+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 ) {hw/9pfs/9p.h +1
-1@@ -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;
In $SUBJECT it is called GHashTable, not GHashMap
Quoted 10 lines · 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.
Quoted 5 lines
Signed-off-by Linus Heckemann <[email protected]>--- hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------ hw/9pfs/9p.h | 2 +- 2 files changed, 69 insertions(+), 63 deletions(-)
With regards,
Daniel
Signature · 3 lines
|: 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 :|
PATCH 1/1 9pfs: use GHashTable for fid table
In reply to Linus HeckemannThe 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.
--- hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------ hw/9pfs/9p.h | 2 +- 2 files changed, 69 insertions(+), 63 deletions(-)
hw/9pfs/9p.c +68 -62
@@ -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);
hw/9pfs/9p.h +1 -1
@@ -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;
Signature · 1 line
2.36.0
Re: [PATCH v2] 9pfs: use GHashTable for fid table
Quoted 10 lines · 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.
Quoted 5 lines
Signed-off-by Linus Heckemann <[email protected]>--- 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
Re: [PATCH] 9pfs: use GHashTable for fid table
In reply to Linus HeckemannHi Linus,
Some more comments below.
Quoted 141 lines · On Mon, 5 Sep 2022 17:03:00 +0200 Linus Heckemann <[email protected]> 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 <[email protected]>--- hw/9pfs/9p.c | 130 +++++++++++++++++++++++++++------------------------ hw/9pfs/9p.h | 2 +- 2 files changed, 69 insertions(+), 63 deletions(-)hw/9pfs/9p.c +37
-40@@ -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;
hw/9pfs/9p.c static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path) · line 524
Quoted 10 lines
hw/9pfs/9p.c +4
-4+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 !
hw/9pfs/9p.c static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path) · line 533
Quoted 6 lines
hw/9pfs/9p.c +0
-0/* * 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.
hw/9pfs/9p.c static int coroutine_fn v9fs_mark_fids_unreclaim(V9fsPDU *pdu, V9fsPath *path) · line 537
Quoted 5 lines
hw/9pfs/9p.c +4
-1-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().
Quoted 31 lines
hw/9pfs/9p.c +7
-10+*/ + 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);
hw/9pfs/9p.c static void coroutine_fn virtfs_reset(V9fsPDU *pdu) · line 580
Quoted 10 lines
hw/9pfs/9p.c +1
-4/* 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...
hw/9pfs/9p.c static void coroutine_fn virtfs_reset(V9fsPDU *pdu) · line 579
Quoted 5 lines
hw/9pfs/9p.c +1
-0fidp->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:
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/[email protected]/
[3] https://github.com/stefanha/git-publish
Quoted 79 lines
hw/9pfs/9p.c +14
-3}#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);hw/9pfs/9p.h +1
-1@@ -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;