From patchwork Thu Dec 12 16:38:34 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: "Dr. David Alan Gilbert" X-Patchwork-Id: 11288913 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 9885814B7 for ; Thu, 12 Dec 2019 17:42:03 +0000 (UTC) Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 6F26E214AF for ; Thu, 12 Dec 2019 17:42:03 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="ex6YU7gS" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 6F26E214AF Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Received: from localhost ([::1]:34860 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ifSTR-0004dj-3f for patchwork-qemu-devel@patchwork.kernel.org; Thu, 12 Dec 2019 12:42:01 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:58507) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ifRWQ-0006yP-P7 for qemu-devel@nongnu.org; Thu, 12 Dec 2019 11:41:04 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ifRWP-0003fc-9d for qemu-devel@nongnu.org; Thu, 12 Dec 2019 11:41:02 -0500 Received: from us-smtp-delivery-1.mimecast.com ([205.139.110.120]:26117 helo=us-smtp-1.mimecast.com) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1ifRWP-0003ek-4f for qemu-devel@nongnu.org; Thu, 12 Dec 2019 11:41:01 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1576168860; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=sVR0S2kuSuY8E45IqUFeGJjMlxxCDS3mETFeqkFImwQ=; b=ex6YU7gSJw8i2agmLgbv6JtPIcJZmnQT4TjFOI5DKtYJPsB91F8tRiWJ/ePhqPuaF53n5a 5/+zEyVxZxrAxImnshHq/++X5sbS/fvnDUJ6pYE2CQkVF7/rGEemY0dgEakxluj2Yft0Zk HzSy9+sqpGkxNRdkwMJVbJtYh6TWFTU= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-154-we4zCQytMyeXW5_PclPcVQ-1; Thu, 12 Dec 2019 11:40:59 -0500 Received: from smtp.corp.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 33FE6800D5A for ; Thu, 12 Dec 2019 16:40:58 +0000 (UTC) Received: from dgilbert-t580.localhost (ovpn-116-226.ams2.redhat.com [10.36.116.226]) by smtp.corp.redhat.com (Postfix) with ESMTP id 581A860BF3; Thu, 12 Dec 2019 16:40:57 +0000 (UTC) From: "Dr. David Alan Gilbert (git)" To: qemu-devel@nongnu.org, stefanha@redhat.com, vgoyal@redhat.com Subject: [PATCH 074/104] virtiofsd: passthrough_ll: use hashtable Date: Thu, 12 Dec 2019 16:38:34 +0000 Message-Id: <20191212163904.159893-75-dgilbert@redhat.com> In-Reply-To: <20191212163904.159893-1-dgilbert@redhat.com> References: <20191212163904.159893-1-dgilbert@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.12 X-MC-Unique: we4zCQytMyeXW5_PclPcVQ-1 X-Mimecast-Spam-Score: 0 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 205.139.110.120 X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" From: Miklos Szeredi Improve performance of inode lookup by using a hash table. Signed-off-by: Miklos Szeredi Signed-off-by: Dr. David Alan Gilbert Signed-off-by: Liu Bo Reviewed-by: Daniel P. Berrangé --- tools/virtiofsd/passthrough_ll.c | 81 ++++++++++++++++++-------------- 1 file changed, 45 insertions(+), 36 deletions(-) diff --git a/tools/virtiofsd/passthrough_ll.c b/tools/virtiofsd/passthrough_ll.c index cd26db74cf..bbc5f0981e 100644 --- a/tools/virtiofsd/passthrough_ll.c +++ b/tools/virtiofsd/passthrough_ll.c @@ -85,13 +85,15 @@ struct lo_map { ssize_t freelist; }; +struct lo_key { + ino_t ino; + dev_t dev; +}; + struct lo_inode { - struct lo_inode *next; /* protected by lo->mutex */ - struct lo_inode *prev; /* protected by lo->mutex */ int fd; bool is_symlink; - ino_t ino; - dev_t dev; + struct lo_key key; uint64_t refcount; /* protected by lo->mutex */ fuse_ino_t fuse_ino; }; @@ -120,7 +122,8 @@ struct lo_data { int timeout_set; int readdirplus_set; int readdirplus_clear; - struct lo_inode root; /* protected by lo->mutex */ + struct lo_inode root; + GHashTable *inodes; /* protected by lo->mutex */ struct lo_map ino_map; /* protected by lo->mutex */ struct lo_map dirp_map; /* protected by lo->mutex */ struct lo_map fd_map; /* protected by lo->mutex */ @@ -574,7 +577,7 @@ retry: } goto fail_unref; } - if (stat.st_dev != inode->dev || stat.st_ino != inode->ino) { + if (stat.st_dev != inode->key.dev || stat.st_ino != inode->key.ino) { if (!retries) { fuse_log(FUSE_LOG_WARNING, "lo_parent_and_name: failed to match last\n"); @@ -754,19 +757,20 @@ out_err: static struct lo_inode *lo_find(struct lo_data *lo, struct stat *st) { struct lo_inode *p; - struct lo_inode *ret = NULL; + struct lo_key key = { + .ino = st->st_ino, + .dev = st->st_dev, + }; pthread_mutex_lock(&lo->mutex); - for (p = lo->root.next; p != &lo->root; p = p->next) { - if (p->ino == st->st_ino && p->dev == st->st_dev) { - assert(p->refcount > 0); - ret = p; - ret->refcount++; - break; - } + p = g_hash_table_lookup(lo->inodes, &key); + if (p) { + assert(p->refcount > 0); + p->refcount++; } pthread_mutex_unlock(&lo->mutex); - return ret; + + return p; } static int lo_do_lookup(fuse_req_t req, fuse_ino_t parent, const char *name, @@ -811,8 +815,6 @@ static int lo_do_lookup(fuse_req_t req, fuse_ino_t parent, const char *name, close(newfd); newfd = -1; } else { - struct lo_inode *prev, *next; - saverr = ENOMEM; inode = calloc(1, sizeof(struct lo_inode)); if (!inode) { @@ -823,17 +825,12 @@ static int lo_do_lookup(fuse_req_t req, fuse_ino_t parent, const char *name, inode->refcount = 1; inode->fd = newfd; newfd = -1; - inode->ino = e->attr.st_ino; - inode->dev = e->attr.st_dev; + inode->key.ino = e->attr.st_ino; + inode->key.dev = e->attr.st_dev; pthread_mutex_lock(&lo->mutex); inode->fuse_ino = lo_add_inode_mapping(req, inode); - prev = &lo->root; - next = prev->next; - next->prev = inode; - inode->next = next; - inode->prev = prev; - prev->next = inode; + g_hash_table_insert(lo->inodes, &inode->key, inode); pthread_mutex_unlock(&lo->mutex); } e->ino = inode->fuse_ino; @@ -1194,14 +1191,8 @@ static void unref_inode_lolocked(struct lo_data *lo, struct lo_inode *inode, assert(inode->refcount >= n); inode->refcount -= n; if (!inode->refcount) { - struct lo_inode *prev, *next; - - prev = inode->prev; - next = inode->next; - next->prev = prev; - prev->next = next; - lo_map_remove(&lo->ino_map, inode->fuse_ino); + g_hash_table_remove(lo->inodes, &inode->key); pthread_mutex_unlock(&lo->mutex); close(inode->fd); free(inode); @@ -1401,7 +1392,7 @@ static void lo_do_readdir(fuse_req_t req, fuse_ino_t ino, size_t size, /* Hide root's parent directory */ if (dinode == &lo->root && strcmp(name, "..") == 0) { - e.attr.st_ino = lo->root.ino; + e.attr.st_ino = lo->root.key.ino; e.attr.st_mode = DT_DIR << 12; } @@ -2402,11 +2393,26 @@ static void setup_root(struct lo_data *lo, struct lo_inode *root) } root->fd = fd; - root->ino = stat.st_ino; - root->dev = stat.st_dev; + root->key.ino = stat.st_ino; + root->key.dev = stat.st_dev; root->refcount = 2; } +static guint lo_key_hash(gconstpointer key) +{ + const struct lo_key *lkey = key; + + return (guint)lkey->ino + (guint)lkey->dev; +} + +static gboolean lo_key_equal(gconstpointer a, gconstpointer b) +{ + const struct lo_key *la = a; + const struct lo_key *lb = b; + + return la->ino == lb->ino && la->dev == lb->dev; +} + int main(int argc, char *argv[]) { struct fuse_args args = FUSE_ARGS_INIT(argc, argv); @@ -2424,7 +2430,7 @@ int main(int argc, char *argv[]) umask(0); pthread_mutex_init(&lo.mutex, NULL); - lo.root.next = lo.root.prev = &lo.root; + lo.inodes = g_hash_table_new(lo_key_hash, lo_key_equal); lo.root.fd = -1; lo.root.fuse_ino = FUSE_ROOT_ID; lo.cache = CACHE_AUTO; @@ -2562,6 +2568,9 @@ err_out2: err_out1: fuse_opt_free_args(&args); + if (lo.inodes) { + g_hash_table_destroy(lo.inodes); + } lo_map_destroy(&lo.fd_map); lo_map_destroy(&lo.dirp_map); lo_map_destroy(&lo.ino_map);