From nobody Tue May 21 22:18:07 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org ARC-Seal: i=1; a=rsa-sha256; t=1662390292; cv=none; d=zohomail.com; s=zohoarc; b=kmTFJkzvBSEqL1ZbyikI+LUzpp3ZJmQqZBaIOVkh5FCLf3JxndCMievwBRYPCthiao/qR4dU1Ov2Lip10fRBY7TrO0AQWKI2GzSwUf/PlXdUgA0iL/m1jVedxPOd52URoqdl2o7N1j3Z43MsHggNbeF1fnlVIPeHaPICRX7S9Vo= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1662390292; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=cSbD5N5MA6lCZ/i7K+GNHmE9NRHF6raQSAidxxJ2PcY=; b=AvsLqilIkBMxnyLdKA/x+Op+MZUJVtUumy4mBPDZ++8cmGMoB+kdzIhfhJ6hBM//O83w+sK02D4w8Zmz3xjk8EhjdlAGjsmptfdVLUIKsIyhHsKtoQRtldcw4Ji8hLKjNuYMwRvNSI2haV3KNNq6793P27Y/RsZVCTda3pe+86c= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1662390291691295.9952739626699; Mon, 5 Sep 2022 08:04:51 -0700 (PDT) Received: from localhost ([::1]:46512 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oVDeb-0003aE-Pl for importer@patchew.org; Mon, 05 Sep 2022 11:04:49 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:52450) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oVDdP-0002rs-12 for qemu-devel@nongnu.org; Mon, 05 Sep 2022 11:03:35 -0400 Received: from sosiego.soundray.org ([2a01:4f8:c2c:a9a0::1]:56328) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oVDdM-0005jU-J4 for qemu-devel@nongnu.org; Mon, 05 Sep 2022 11:03:34 -0400 From: Linus Heckemann DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sphalerite.org; s=sosiego; t=1662390206; bh=cSbD5N5MA6lCZ/i7K+GNHmE9NRHF6raQSAidxxJ2PcY=; h=From:To:Cc:Subject:Date:In-Reply-To:References; b=Ju9edQlr5XS97LNoTnwTbja8mzuQSXV0tkXZlPhxS6DH+tNP8C2BZz/rUDz0mEPpl cvUK/cSNWoa2ZRDorCz16gXDcJlSThhi2fHbIKJNz6pJ9stj49Hl21QYCeBc1mSOZz 7cE1zqPDXuAj98ARM1iaziZdWai3JtcXh/wYRv2Y= To: qemu-devel@nongnu.org, Greg Kurz , Christian Schoenebeck , =?UTF-8?q?Philippe=20Mathieu-Daud=C3=A9?= , =?UTF-8?q?Daniel=20P=20=2E=20Berrang=C3=A9?= Cc: Linus Heckemann Subject: [PATCH] 9pfs: use GHashTable for fid table Date: Mon, 5 Sep 2022 17:03:00 +0200 Message-Id: <20220905150300.3794196-1-git@sphalerite.org> In-Reply-To: <20220903150327.2780127-1-git@sphalerite.org> References: <20220903150327.2780127-1-git@sphalerite.org> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=2a01:4f8:c2c:a9a0::1; envelope-from=linus@sphalerite.org; helo=sosiego.soundray.org X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: pass (identity @sphalerite.org) X-ZM-MESSAGEID: 1662390292999100001 Content-Type: text/plain; charset="utf-8" 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 Reviewed-by: Greg Kurz Reviewed-by: Philippe Mathieu-Daud=C3=A9 --- 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 *pd= u, int32_t fid) V9fsFidState *f; V9fsState *s =3D pdu->s; =20 - QSIMPLEQ_FOREACH(f, &s->fid_list, next) { - BUG_ON(f->clunked); - if (f->fid =3D=3D 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 =3D 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 |=3D FID_REFERENCED; - return f; + f =3D 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 =3D 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 |=3D FID_REFERENCED; + return f; } return NULL; } @@ -317,12 +315,9 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t f= id) { V9fsFidState *f; =20 - 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 =3D=3D fid) { - return NULL; - } + return NULL; } f =3D g_new0(V9fsFidState, 1); f->fid =3D fid; @@ -333,7 +328,7 @@ static V9fsFidState *alloc_fid(V9fsState *s, int32_t fi= d) * reclaim won't close the file descriptor */ f->flags |=3D FID_REFERENCED; - QSIMPLEQ_INSERT_TAIL(&s->fid_list, f, next); + g_hash_table_insert(s->fids, GINT_TO_POINTER(fid), f); =20 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; =20 - QSIMPLEQ_FOREACH(fidp, &s->fid_list, next) { - if (fidp->fid =3D=3D fid) { - QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next); - fidp->clunked =3D true; - return fidp; - } + if (g_hash_table_steal_extended(s->fids, GINT_TO_POINTER(fid), + NULL, (gpointer *) &fidp)) { + fidp->clunked =3D true; + return fidp; } return NULL; } @@ -439,10 +432,15 @@ void coroutine_fn v9fs_reclaim_fd(V9fsPDU *pdu) int reclaim_count =3D 0; V9fsState *s =3D pdu->s; V9fsFidState *f; + GHashTableIter iter; + gpointer fid; + + g_hash_table_iter_init(&iter, s->fids); + QSLIST_HEAD(, V9fsFidState) reclaim_list =3D QSLIST_HEAD_INITIALIZER(reclaim_list); =20 - 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(V9fs= PDU *pdu, V9fsPath *path) { int err; V9fsState *s =3D pdu->s; - V9fsFidState *fidp, *fidp_next; + V9fsFidState *fidp; + gpointer fid; + GHashTableIter iter; =20 - fidp =3D QSIMPLEQ_FIRST(&s->fid_list); - if (!fidp) { - return 0; - } + g_hash_table_iter_init(&iter, s->fids); =20 /* * 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(V9fsP= DU *pdu, V9fsPath *path) * iteration after we could get a reference on the next fid. Start with * the first one. */ - for (fidp->ref++; fidp; fidp =3D 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 =3D=3D 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(V9fsP= DU *pdu, V9fsPath *path) } } =20 - fidp_next =3D QSIMPLEQ_NEXT(fidp, next); - - if (fidp_next) { - /* - * Ensure the next fid survives a potential clunk request duri= ng - * 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 =3D pdu->s; V9fsFidState *fidp; + gpointer fid; + GHashTableIter iter; + + g_hash_table_iter_init(&iter, s->fids); =20 /* Free all fids */ - while (!QSIMPLEQ_EMPTY(&s->fid_list)) { - /* Get fid */ - fidp =3D QSIMPLEQ_FIRST(&s->fid_list); + while (g_hash_table_iter_next(&iter, &fid, (gpointer *) &fidp)) { fidp->ref++; =20 /* Clunk fid */ - QSIMPLEQ_REMOVE(&s->fid_list, fidp, V9fsFidState, next); fidp->clunked =3D true; =20 put_fid(pdu, fidp); } + g_hash_table_remove_all(s->fids); } =20 #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 =3D pdu->s; V9fsFidState *dirfidp =3D NULL; + GHashTableIter iter; + gpointer fid; =20 v9fs_path_init(&new_path); if (newdirfid !=3D -1) { @@ -3238,11 +3235,13 @@ static int coroutine_fn v9fs_complete_rename(V9fsPD= U *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 *p= du, V9fsPath *olddir, V9fsPath oldpath, newpath; V9fsState *s =3D pdu->s; int err; + GHashTableIter iter; + gpointer fid; =20 v9fs_path_init(&oldpath); v9fs_path_init(&newpath); @@ -3336,7 +3337,8 @@ static int coroutine_fn v9fs_fix_fid_paths(V9fsPDU *p= du, 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 V9= fsTransport *t, s->ctx.fmode =3D fse->fmode; s->ctx.dmode =3D fse->dmode; =20 - QSIMPLEQ_INIT(&s->fid_list); + s->fids =3D g_hash_table_new(NULL, NULL); qemu_co_rwlock_init(&s->rename_lock); =20 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 =3D 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; --=20 2.36.0