From patchwork Tue Sep 19 16:31:52 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Robin Murphy X-Patchwork-Id: 113044 Delivered-To: patch@linaro.org Received: by 10.140.106.117 with SMTP id d108csp5119048qgf; Tue, 19 Sep 2017 09:32:16 -0700 (PDT) X-Google-Smtp-Source: AOwi7QDbxbh0ccK5ikuie914n41Hh9ViTrYMvGPpNniGR2E0cuNDRAUCS2yCBFwAYrBr0ZWD77tF X-Received: by 10.99.95.204 with SMTP id t195mr1869052pgb.68.1505838735962; Tue, 19 Sep 2017 09:32:15 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1505838735; cv=none; d=google.com; s=arc-20160816; b=S+tCMyLgBLyA7YrcBwWztR1j3393np2rTjjvRYwzGi5jIoF31pwnhTHJzW3lEU0ntA XslAL+2v7KAVWQTHONEWF6y+Q2dkqQP5ZzeJd4K62yGPT9xDOuqmqcRRUfxG/v3gtRtz PyAo+YF4WNJYDKTOa/fr273W7wu+h+qI3WBezv41OpnCI3YouwrB4y56ykq2H/oiy97u nkvTneujN9lCMKPiMkgm/mIrj65c1yb5QjKZFTseX/7XXw6OEYc1PnmsjL5SBtSU0Tw8 q1tFiXxV3kP0uDEwFhxQdn08yMfPfJWcprlQ+XnRkQK+ZWCKQMUEw0RCuroTB9MOEhek G8yw== 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=pGW6hMdSgA/mPQn6urDFZyyGYSwmpg2PrWDpe7Zra6Y=; b=nRFva3Y/Y6Os/6wb9LrPMF6st43VV0R5IKnDuDeuJTT7WAecki40g2RPkUaKRpXrpi ffDC9T7c7m/AGj2R0Vz0cZIQAnD2ilY4ApGEd0ralVfmVoevwwyVHs7HZl27Rd6B/g8Z ocM0PIyR5TnoAnGyKKD+vciLrn2xoOsn1omXS8emqxjB7lS8MOPgXCyAOLdF2sUG6edp rGnBXKC4JvhniTZaM2CJw6lpRQlL1WM0DNLTKclX0c1lbaDbv91C69ZFt8nYGo0bkGGw jicGUiZnP4igioAfE6yqcQyEB0wOJcOpLXz0M81UqjQpFbU4BZ3N04ivmSeuHi/6Hfxo 9eLg== 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 l36si6801443plg.198.2017.09.19.09.32.15; Tue, 19 Sep 2017 09:32:15 -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 S1751594AbdISQcM (ORCPT + 26 others); Tue, 19 Sep 2017 12:32:12 -0400 Received: from foss.arm.com ([217.140.101.70]:52916 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751542AbdISQcK (ORCPT ); Tue, 19 Sep 2017 12:32:10 -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 A366A1435; Tue, 19 Sep 2017 09:32:09 -0700 (PDT) Received: from e110467-lin.cambridge.arm.com (e110467-lin.cambridge.arm.com [10.1.210.88]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 635B43F58C; Tue, 19 Sep 2017 09:32:08 -0700 (PDT) From: Robin Murphy To: joro@8bytes.org Cc: iommu@lists.linux-foundation.org, thunder.leizhen@huawei.com, nwatters@codeaurora.org, tomasz.nowicki@caviumnetworks.com, linux-kernel@vger.kernel.org Subject: [PATCH v4 1/6] iommu/iova: Optimise rbtree searching Date: Tue, 19 Sep 2017 17:31:52 +0100 Message-Id: <9d6aff3f458a54d210eabdaa38ee6baa0a901a3a.1505829018.git.robin.murphy@arm.com> X-Mailer: git-send-email 2.13.4.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 Tested-by: Nate Watterson [rm: rewrote commit message to clarify] Signed-off-by: Robin Murphy --- v4: No change drivers/iommu/iova.c | 9 +++------ 1 file changed, 3 insertions(+), 6 deletions(-) -- 2.13.4.dirty diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c index 33edfa794ae9..f129ff4f5c89 100644 --- a/drivers/iommu/iova.c +++ b/drivers/iommu/iova.c @@ -342,15 +342,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;