From patchwork Tue Jul 18 16:57:19 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Robin Murphy X-Patchwork-Id: 108162 Delivered-To: patch@linaro.org Received: by 10.182.45.195 with SMTP id p3csp6155170obm; Tue, 18 Jul 2017 10:05:26 -0700 (PDT) X-Received: by 10.84.137.1 with SMTP id 1mr2715397plm.75.1500397526640; Tue, 18 Jul 2017 10:05:26 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1500397526; cv=none; d=google.com; s=arc-20160816; b=pNaIcEjKXBZE0eyrFZsSjHagS8RRuT39VVCB/wNGpRbPMyLLRQRCu2aVkJvmc3ltY3 nAaLJM79sg1hqgdEAbQfonHylpKyHh91v13dzar+k9w4l3ECn3RZqQuSXAfO5Rur1xIb WsE/qGQvKsZSOYs9/VtqbhfVehcmrOjCOdk+w3UgdPBPRG6a8wR+y9jUATAYj4hbQs3c I+ZEa7xYABlQCfLdFc0P4lNk/ivS6sPNXVfOd0w2EW8eVuAUjdOjm6SpRHwWDez+mP9N CCuo7Exy/CExeUR9qGhVhS9U/3jJdSKbr91ymXM0SQzwOE2HclAcygqRrKoEZFVvnaCF a75A== 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=fmOeAdiJtpW3/Z+KIb/teRPCKkk+TDfPXtkL7u76Rac=; b=D3ZSnZgMWfUtViIQ/Fini4M6RCgx/H1GcQaWD+rZ3JDTiQc0TrJAFjTYc70dJKN+Ox Me9z1QcPOAcRjnzCEieJwRPCAHlPcU3ZSHgfMG31CP0JzqvW+Hz8h9DbrDzB4AT14n9B XfkPqR9Jvof4JVnphveB8VzhMBecbfdYhV9/LTC+lqFL6YxVIJN/9GMplluwf6gQDuoe FUljqDIZlCrrwrJhymqPYENOUezqxcP//zpaVTjqpWyiGBnkqebzAbrY3LMFKKAkP5Q+ eil5SOQTpHPTofuPM4WZ10av9M2PmafXtma65EK23yNwXbeBj4KH+glJvxeUtMCdfKSh G6jw== 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 k7si2118662pfc.352.2017.07.18.10.05.26; Tue, 18 Jul 2017 10:05:26 -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 S1752633AbdGRRFY (ORCPT + 25 others); Tue, 18 Jul 2017 13:05:24 -0400 Received: from usa-sjc-mx-foss1.foss.arm.com ([217.140.101.70]:56166 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752201AbdGRRAR (ORCPT ); Tue, 18 Jul 2017 13:00:17 -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 5476715AD; Tue, 18 Jul 2017 10:00:17 -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 889E83F577; Tue, 18 Jul 2017 10:00:15 -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 1/4] iommu/iova: Optimise rbtree searching Date: Tue, 18 Jul 2017 17:57:19 +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 [rm: rewrote commit message to clarify] Signed-off-by: Robin Murphy --- 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;