Received: by 2002:a05:7412:2a8c:b0:e2:908c:2ebd with SMTP id u12csp1391252rdh; Mon, 25 Sep 2023 11:13:52 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFILh0SOanG3MMlArg/zurYUg3meHw6IuClNFdhJlZpplOW5mq+2QfTt3uOXY4N8Qet7xV3 X-Received: by 2002:a05:6a00:b56:b0:68e:369b:a123 with SMTP id p22-20020a056a000b5600b0068e369ba123mr9303997pfo.1.1695665632639; Mon, 25 Sep 2023 11:13:52 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695665632; cv=none; d=google.com; s=arc-20160816; b=0B5lbZN1GCwe763M0qoF8sqOJY9osCsryraMaKmfVgRVdC7CID49d7bxSCVLchx9A1 hS8K+O4w/O+Q66gtS1ESAb1COSNnvWoZ6VjavGG0+kklFZMY3y9fkVRxUMpVQf8bMka+ uZ/242XlCg4Usim2J3x4+VLgHiU2EXuNHOd7DX7n5DAR77xdNjtlHpGh5vni4Z45uGi4 ZybA5Q49XbgzSvHfM4dOiRAEvaAtydTZZFizFaPZpEZ44UcHAvdZUXZu+obP9oS+Qrno 4HWYz+4FD3wlGvzAm8Xu8/UBSYNMEtUWic1mu2sq2mxmJ5MAvZbkPMnsZsF74PAbAL3v e9uQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:in-reply-to:content-disposition:mime-version :references:message-id:subject:cc:to:from:date:dkim-signature; bh=GBCbZq0gPEh0kYOz+rqbSiHwhhhlG+FWGqAp3fMEJGQ=; fh=fA9i0YqD1zjhR9O7wx3ReWhHz5ofPMwp6TWqze4SP0w=; b=i6NSzbULRXVP9GYiRqgkhKejMJcEdsFSebsmLZiAbDT4dfLgpxa8fAhH6sTms6Yldy +uhYtrqNoH7zvga7cmQCvtnrJXZ1OZk6eYdPF61eIuqA5uWqOAfrYbqRaJ7og/3WOIu/ Hxg2VQCgHDEb9xSNuRLEDdf8gfEIkXY3kLgicZrrBqw42AbOrgBTGq0vg72hvCY6IIo+ EW2f9Aj/wgv56hCNUMtB4f2wrRRdpCrTAkMG+3MpYl7h19YzQQtT0Tt4SLTdMi89Jq3g Dtp7C3wvQ1+B9Z9wyaaibY3Jl0IrKMY5QaGLiUVeibnJRy+Owkb8BtJueaGH4NgukPgf apIw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@8bytes.org header.s=default header.b=tZLsAxko; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from snail.vger.email (snail.vger.email. [2620:137:e000::3:7]) by mx.google.com with ESMTPS id bz14-20020a056a02060e00b00569465f387dsi12564426pgb.161.2023.09.25.11.13.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Sep 2023 11:13:52 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) client-ip=2620:137:e000::3:7; Authentication-Results: mx.google.com; dkim=pass header.i=@8bytes.org header.s=default header.b=tZLsAxko; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by snail.vger.email (Postfix) with ESMTP id BFD2380E06A7; Mon, 25 Sep 2023 01:13:30 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at snail.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232921AbjIYIN3 (ORCPT + 99 others); Mon, 25 Sep 2023 04:13:29 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55376 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232912AbjIYINJ (ORCPT ); Mon, 25 Sep 2023 04:13:09 -0400 Received: from mail.8bytes.org (mail.8bytes.org [85.214.250.239]) by lindbergh.monkeyblade.net (Postfix) with ESMTP id DE4181723 for ; Mon, 25 Sep 2023 01:12:17 -0700 (PDT) Received: from 8bytes.org (pd9fe9df8.dip0.t-ipconnect.de [217.254.157.248]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-256) server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mail.8bytes.org (Postfix) with ESMTPSA id 669CF1A2200; Mon, 25 Sep 2023 10:12:15 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=8bytes.org; s=default; t=1695629535; bh=rvI403sXHjIFnb/aVy8uQZA0DiZlvQIsvyech7TF9z8=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=tZLsAxkobYW4nXTZPQyTTI0CxJ1RLZBFxCnfvN4NEPAm86DIM+5jExytbxov5okMw dzsjzSrCYlu5KOGlO4ynkW2vVywUEEYlCgVyaA0z9mGgynrXuNq/LcsDZO26r3fQT7 NV3yr15KdexSUtzI3pKvfERl+JWYijQxTp+i0WkPudGEfEto/ePIYkNIyDfcc/30D7 Rww5T8BdEnrp7T0usBJYfZO7nrJZ91kaMKhSzStj5naP7t4DVksnq4l4pKXs7XHAzN W/LcRH51uY+IJD0iZrsZoBjt+iuYMv2XExCIOzPx6rzgtB3cugXOIXO200URKWmsr1 icn2IFHaTNEvw== Date: Mon, 25 Sep 2023 10:12:14 +0200 From: Joerg Roedel To: Huang Jiaqing Cc: kvm@vger.kernel.org, iommu@lists.linux.dev, linux-kernel@vger.kernel.org, will@kernel.org, robin.murphy@arm.com, kevin.tian@intel.com, baolu.lu@linux.intel.com, jacob.jun.pan@linux.intel.com, yi.l.liu@intel.com, yi.y.sun@intel.com Subject: Re: [PATCH] iommu/vt-d: Introduce a rb_tree for looking up device Message-ID: References: <20230821071659.123981-1-jiaqing.huang@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20230821071659.123981-1-jiaqing.huang@intel.com> X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (snail.vger.email [0.0.0.0]); Mon, 25 Sep 2023 01:13:30 -0700 (PDT) On Mon, Aug 21, 2023 at 12:16:59AM -0700, Huang Jiaqing wrote: > The existing IO page fault handler locates the PCI device by calling > pci_get_domain_bus_and_slot(), which searches the list of all PCI > devices until the desired PCI device is found. This is inefficient > because the algorithm efficiency of searching a list is O(n). In the > critical path of handling an IO page fault, this can cause a significant > performance bottleneck. Can you elaborate a little more on the 'significant performance bottleneck' part? Where do you see this as a problem? Regards, Joerg