From patchwork Thu Jan 23 11:58:06 2020 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: 1227973 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=nongnu.org (client-ip=209.51.188.17; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=faOmLRIo; dkim-atps=neutral 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 ozlabs.org (Postfix) with ESMTPS id 483Nhy6xhBz9sP3 for ; Fri, 24 Jan 2020 00:41:22 +1100 (AEDT) Received: from localhost ([::1]:57190 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iucjY-0002bX-Fu for incoming@patchwork.ozlabs.org; Thu, 23 Jan 2020 08:41:20 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:41254) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iubAJ-0003v5-0Z for qemu-devel@nongnu.org; Thu, 23 Jan 2020 07:00:52 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1iubAD-00068B-Pq for qemu-devel@nongnu.org; Thu, 23 Jan 2020 07:00:47 -0500 Received: from us-smtp-1.mimecast.com ([207.211.31.81]:20974 helo=us-smtp-delivery-1.mimecast.com) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1iubAD-00067F-6o for qemu-devel@nongnu.org; Thu, 23 Jan 2020 07:00:45 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1579780845; 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=uUS2SXabuzTnbWWfW9WfG206NGyKVphzTRYIpPi52s0=; b=faOmLRIo4kLGxxyIru9IAZtkO3khlVW62Yga82QxLBg31bQTYNntDYrZcPnvA1ZWQZgRIY S9AztUBCm7Pt+g0VleJxR+i84fCYSR6wFRMSf5xQagHnjFj8EFaxSYNjbuXkT+PpH+FX0h 4AaXv5NCUWbKYS+aX1gRTA3AO59Zu7M= 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-217-FyIe7X8SP9CaLgZbILGwkQ-1; Thu, 23 Jan 2020 07:00:42 -0500 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 0C3348010E7 for ; Thu, 23 Jan 2020 12:00:42 +0000 (UTC) Received: from dgilbert-t580.localhost (unknown [10.36.118.0]) by smtp.corp.redhat.com (Postfix) with ESMTP id 56F9485757; Thu, 23 Jan 2020 12:00:41 +0000 (UTC) From: "Dr. David Alan Gilbert (git)" To: qemu-devel@nongnu.org, stefanha@redhat.com Subject: [PULL 076/111] virtiofsd: passthrough_ll: use hashtable Date: Thu, 23 Jan 2020 11:58:06 +0000 Message-Id: <20200123115841.138849-77-dgilbert@redhat.com> In-Reply-To: <20200123115841.138849-1-dgilbert@redhat.com> References: <20200123115841.138849-1-dgilbert@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-MC-Unique: FyIe7X8SP9CaLgZbILGwkQ-1 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 207.211.31.81 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+incoming=patchwork.ozlabs.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é Signed-off-by: Dr. David Alan Gilbert --- 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 b40f2874a7..b176a314d6 100644 --- a/tools/virtiofsd/passthrough_ll.c +++ b/tools/virtiofsd/passthrough_ll.c @@ -84,13 +84,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; }; @@ -119,7 +121,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 */ @@ -573,7 +576,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, "%s: failed to match last\n", __func__); @@ -753,19 +756,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, @@ -810,8 +814,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) { @@ -822,17 +824,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; @@ -1162,14 +1159,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); @@ -1369,7 +1360,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; } @@ -2370,11 +2361,26 @@ static void setup_root(struct lo_data *lo, struct lo_inode *root) root->is_symlink = false; 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); @@ -2392,7 +2398,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; @@ -2522,6 +2528,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);