From patchwork Tue Aug 22 15:17:42 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Robin Murphy X-Patchwork-Id: 110686 Delivered-To: patch@linaro.org Received: by 10.140.95.78 with SMTP id h72csp2828504qge; Tue, 22 Aug 2017 08:17:59 -0700 (PDT) X-Received: by 10.84.211.66 with SMTP id b60mr1168780pli.150.1503415079879; Tue, 22 Aug 2017 08:17:59 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1503415079; cv=none; d=google.com; s=arc-20160816; b=G6RkYkW6c1ANiKElsXgh0C2qpQ76SQc+RvDpg+VhuPzqnO3i9Xvrdlnj304A3Ln4FR k+XtuHcPudZHqWxb1Ma1W8wgQUl6tMZIuSVH58leyfIzPPCdc9tt+OpBU/kOePcAE+7o AXB9yOrnztKO8rdlmy7xSEC9dmkTiweVv0t+j+It0Fw0h2RSpcO28Z/Hq+RgqRcTSHi4 z0va7tqqGLeeZ92CPwku3dCmZKrdBcGEFhLTR6WYadin7AOzDkig5lSSq3yisKm6ydVi +e1ta0iSIl244yESGYcLRiKxVV/V+Y/9i4gDdkOaJi7Q1Fv91bxplv44+JqFELoOhBuH eCDw== 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=MW83RV+JohJBXjKrsgdnaFYBOErcD1AJz1TSlVIvmMY=; b=oLXxdn7ZEpK45AkqCB2pRTWTrCAUX3BLycbzruxlo0wIp0XsMSFMFizeBVU4+RxPg9 CPJzHp/JFjv0Szk+i2HWYjlwedlAHyJpjXEMXnYExMnsTTawIYvL1EVLB2T0wQLZhUgV MF4MbZxCIKlz9ZSEwyHW4MukiY5cmwxMhk7qbS5AQHa/NHNcAmxipN1kNaIHKpZrVPZl ffw6XvtkOIaeAehpAbL4h5yZjM52Y50tYCJGm7GgytjVJhkGlpxg3f2kV3m3NfWB9Lr7 mdA/dsHeQrBV0ZPajc/omuZ+jNRZrpYBp2V5yV6rc20XzK9eui+ixgapVFVO1mQ24FvH 9sCQ== 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 u16si9858378plk.296.2017.08.22.08.17.59; Tue, 22 Aug 2017 08:17:59 -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 S933166AbdHVPR5 (ORCPT + 26 others); Tue, 22 Aug 2017 11:17:57 -0400 Received: from foss.arm.com ([217.140.101.70]:45416 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932941AbdHVPRy (ORCPT ); Tue, 22 Aug 2017 11:17:54 -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 90A8B15A2; Tue, 22 Aug 2017 08:17:54 -0700 (PDT) Received: from e110467-lin.cambridge.arm.com (e110467-lin.cambridge.arm.com [10.1.211.24]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 3B2D03F577; Tue, 22 Aug 2017 08:17:53 -0700 (PDT) From: Robin Murphy To: joro@8bytes.org Cc: iommu@lists.linux-foundation.org, linux-kernel@vger.kernel.org, thunder.leizhen@huawei.com, ard.biesheuvel@linaro.org, nwatters@codeaurora.org, ray.jui@broadcom.com Subject: [PATCH v3 1/4] iommu/iova: Optimise rbtree searching Date: Tue, 22 Aug 2017 16:17:42 +0100 Message-Id: <36e6a673dea7e22210cb9e28bbd50b3b78d7d835.1503412074.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 [rm: rewrote commit message to clarify] Signed-off-by: Robin Murphy --- v3: 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 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;