From patchwork Thu Sep 21 15:52: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: 113288 Delivered-To: patch@linaro.org Received: by 10.140.106.117 with SMTP id d108csp2185286qgf; Thu, 21 Sep 2017 08:53:03 -0700 (PDT) X-Google-Smtp-Source: AOwi7QDsXs/ZEOe217/ZWin5nv4+O75nsNQRZRCThVcWKy8wPgLhoMNzgqlqVdeFeUH84m9EiswT X-Received: by 10.84.212.2 with SMTP id d2mr5956935pli.412.1506009183178; Thu, 21 Sep 2017 08:53:03 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1506009183; cv=none; d=google.com; s=arc-20160816; b=zpxYLenVivthmm/fNH3JoC6siraaxZjnTF5NYeq6cV9qeLQKV2/EyMriMcJyNUqLZL 1B854JgCd9l3oUxGHIRdQdJ5S3noFo8k26xpJ//yOKDumTukb/qkMpWN8FK8W/0z1DE9 B93nHHPPSO/LZl59H+tfOBxK/VSSsultVu8J+O7w22oVVBI24r/j1+W0hXYyUiIIavax lHjwBjYfyhp6FCwPevVEAt69FuzBoRkQ/meKxnjSYv65zpFbMJwG23BntbYyTj74c0CV UMqNCv1dtTGuPCjYIwTCp87okVcnU8HAo6fBnSHEvPYc3CWJpyE6rP9HAVQNf2Xu2ugd Nt/g== 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=EH8k+nbhoh8bCxj+375jkpUrYBPDDYonX627lRw3AKA=; b=tK3jo/dPcFiBVOCAFt3hZppgaqg1Nv1LMDl5nQpB7S/RAf/jIhxVOcVCd+hHjHYvW9 ri19ibDXTm5zqODsuzDcGn5DrdyGi0DuDWyzVTw0OtAX+gNik06I/00sgGnyVZfLgNjK fBLocUleRusxw8WB+65iIEh4NNYHz2/8+JXKsE+PyVtNmw09s8H3VyssYfYK8w0TKT1S Y39pEE2NiJ63NfMXNnaXwk4BFJTWPAypJUpeQ0ReaKXhrkvhpFUihnhk6Ru+IqamB+4v YxNg99TE5LAy7UkOnpkkRGIbc6a/SFK22Yft64WB/VmUSWygVoXHzYButOnQmizYDInX lt+g== 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 d1si1200104pgu.506.2017.09.21.08.53.02; Thu, 21 Sep 2017 08:53:03 -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 S1751750AbdIUPxB (ORCPT + 26 others); Thu, 21 Sep 2017 11:53:01 -0400 Received: from usa-sjc-mx-foss1.foss.arm.com ([217.140.101.70]:48696 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751709AbdIUPw6 (ORCPT ); Thu, 21 Sep 2017 11:52:58 -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 ED4861435; Thu, 21 Sep 2017 08:52:57 -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 97C6B3F578; Thu, 21 Sep 2017 08:52:56 -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, dwoods@mellanox.com, linux-kernel@vger.kernel.org Subject: [PATCH v5 1/6] iommu/iova: Optimise rbtree searching Date: Thu, 21 Sep 2017 16:52:42 +0100 Message-Id: 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 --- v5: 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;