From patchwork Fri Jul 21 11:41:58 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Robin Murphy X-Patchwork-Id: 108474 Delivered-To: patch@linaro.org Received: by 10.140.101.44 with SMTP id t41csp689115qge; Fri, 21 Jul 2017 04:42:21 -0700 (PDT) X-Received: by 10.98.252.87 with SMTP id e84mr7199768pfh.184.1500637341338; Fri, 21 Jul 2017 04:42:21 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1500637341; cv=none; d=google.com; s=arc-20160816; b=sMxKb4f6yRE/5H6MIo/RzeesFajFw/UK7snevBKm+jWoigLsw+c7XH/mhnTQf2Kwn8 Z+akq3Py6BCFjPqB6cmyuUtgwPRKC+PV84NSgYTcpidLaOp2DzDviCW1RADEBtlBPmMT Ud+o2mkFzn+6TfGV6p4ca+gxVVtZb/tdc+/hNEe4tlmtVWe5zxSj7pVTHNvyqVKKPUgi j5jBVanplWXXUoa58oA+pJ+FQR3gsT+T4waDj+KDSFRvWMOzchy6b7rt+pYFGPQvPEaQ cye6nGWNSdjV5l8VyITigbLp62/brj1SPEkzjwCyNAXkjHPAv9B4rNBs0c7ERy68BCcz /fsg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=+9phoOCn5XnHpV2oRdA8m1OrJDFyGbOyWx+3HU5n8pU=; b=0IzymyT4BS+FPCDf7oiA4mY6GF64I/tspc/XU+P5O1W1/MnEJOo/x7bjMtUJ+zTbSD s+3PwtVQ7L1jMRV6iveyvc418qnlP4vOsyozn3RO7DjK95R5ANxWg9V3pk2gVNwKToBN 7TeMWL+1ISJ4DyUIuXf/fTp/UXioar/am9Tv6bUsmxIeg90m6/MWNq89DNkjIjRWJBlc 0+bcKMeoenOelstkytr5tdL1QAFMSIy2mxRcs8ZlDLmlnNjuH3oDXbl1RB06BinwWzig mFOubY4KYMhue+wThSc3+/WoPZh/pVfS5PXxRsmcaeog1YZqxJ+4+47ddM/QnJJ5suj/ uAlQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id d21si3083793pgn.292.2017.07.21.04.42.21; Fri, 21 Jul 2017 04:42:21 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753823AbdGULmS (ORCPT + 25 others); Fri, 21 Jul 2017 07:42:18 -0400 Received: from usa-sjc-mx-foss1.foss.arm.com ([217.140.101.70]:35248 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750802AbdGULmL (ORCPT ); Fri, 21 Jul 2017 07:42:11 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id EB4121596; Fri, 21 Jul 2017 04:42:10 -0700 (PDT) Received: from e110467-lin.cambridge.arm.com (e110467-lin.cambridge.arm.com [10.1.210.24]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 2ABCC3F578; Fri, 21 Jul 2017 04:42:09 -0700 (PDT) From: Robin Murphy To: joro@8bytes.org Cc: iommu@lists.linux-foundation.org, linux-arm-kernel@lists.infradead.org, linux-kernel@vger.kernel.org, dwmw2@infradead.org, thunder.leizhen@huawei.com, lorenzo.pieralisi@arm.com, ard.biesheuvel@linaro.org, Jonathan.Cameron@huawei.com, nwatters@codeaurora.org, ray.jui@broadcom.com Subject: [PATCH v2 1/4] iommu/iova: Optimise rbtree searching Date: Fri, 21 Jul 2017 12:41:58 +0100 Message-Id: X-Mailer: git-send-email 2.12.2.dirty In-Reply-To: References: Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Zhen Lei Checking the IOVA bounds separately before deciding which direction to continue the search (if necessary) results in redundantly comparing both pfns twice each. GCC can already determine that the final comparison op is redundant and optimise it down to 3 in total, but we can go one further with a little tweak of the ordering (which makes the intent of the code that much cleaner as a bonus). Signed-off-by: Zhen Lei Tested-by: Ard Biesheuvel Tested-by: Zhen Lei [rm: rewrote commit message to clarify] Signed-off-by: Robin Murphy --- v2: No change drivers/iommu/iova.c | 9 +++------ 1 file changed, 3 insertions(+), 6 deletions(-) -- 2.12.2.dirty diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c index 246f14c83944..8f7552dc4e04 100644 --- a/drivers/iommu/iova.c +++ b/drivers/iommu/iova.c @@ -289,15 +289,12 @@ private_find_iova(struct iova_domain *iovad, unsigned long pfn) while (node) { struct iova *iova = rb_entry(node, struct iova, node); - /* If pfn falls within iova's range, return iova */ - if ((pfn >= iova->pfn_lo) && (pfn <= iova->pfn_hi)) { - return iova; - } - if (pfn < iova->pfn_lo) node = node->rb_left; - else if (pfn > iova->pfn_lo) + else if (pfn > iova->pfn_hi) node = node->rb_right; + else + return iova; /* pfn falls within iova's range */ } return NULL;