From patchwork Fri Jul 21 11:41:59 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Robin Murphy X-Patchwork-Id: 108476 Delivered-To: patch@linaro.org Received: by 10.140.101.44 with SMTP id t41csp689528qge; Fri, 21 Jul 2017 04:42:49 -0700 (PDT) X-Received: by 10.98.219.130 with SMTP id f124mr7273774pfg.168.1500637369467; Fri, 21 Jul 2017 04:42:49 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1500637369; cv=none; d=google.com; s=arc-20160816; b=DykYHkh70OAg79JY4XwL3OqE6U1fCjeDA6R+nhSQt/TCgZc3Vl9XtYbPQE1IRlCJpJ mLxU5Ll/A+QPHKVsFsbRmgmyPHMrFpVD4o2H2pgDnip2v5af42fEf9+m5RajXwG1Pkp1 OfDzPtfFYRJ3sHQn7KDCdvd3ole8JDonIdtBpjLIgiOHKZ50ZJdZXSu4ZJiPzK0Roh42 X6pLrTrHr/qoHfEzQooj6L+gao8DrzNWFMZUUF/ukvviPEes/2oIeJ0N0svWlssqU3NO F9Btp8pNNTNS6oV72GAxk4edfbW+hzBsvuOc+oMlZRBe8DHbAhDlUM8xTPxurHyZKRPs x+CA== 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=9euJSnES7EyqK9U0FFQJIKYgyudHO+QyvY6T1UV6oZM=; b=Jv/ZKRUpIGPVWX1lGR50KAFqU3Kn4XvHfSUdkPdwYsEFNKH8bMFY56eztHHc3lIx9f tSgc5QGyxU+JFnDNF+zySgU2uu35eEgUxeHFVYZVzovL/g+/u+tah/EXFFJYQAgePImA 2893Oe0ktzHDhp3JY3eiuL++8s6obNxfn6vnmLaU2JBc+xEux0AIK3YXVh50YV6Kj4dz 2tVJCcu2jlZlnyZBK+4sIj/J4rYFwl3/4hPFOJD8BE34KgL+/gOh7JWx6/AtxM0yQwKj D9jUI/c92zSrZMAk6HN/hAx2UOby6aq9d1FgmPU1v2nHbnPXbyZb1eyTrT+CNuNgFYGZ mftA== 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 m8si3008131pgc.582.2017.07.21.04.42.49; Fri, 21 Jul 2017 04:42:49 -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 S1753424AbdGULmR (ORCPT + 25 others); Fri, 21 Jul 2017 07:42:17 -0400 Received: from usa-sjc-mx-foss1.foss.arm.com ([217.140.101.70]:35270 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751065AbdGULmO (ORCPT ); Fri, 21 Jul 2017 07:42:14 -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 D67D515AD; Fri, 21 Jul 2017 04:42:13 -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 152093F578; Fri, 21 Jul 2017 04:42:11 -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 2/4] iommu/iova: Optimise the padding calculation Date: Fri, 21 Jul 2017 12:41:59 +0100 Message-Id: <4f964e56fe39c6ce1c84b8458c3a27dcb51077d4.1500636791.git.robin.murphy@arm.com> 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 The mask for calculating the padding size doesn't change, so there's no need to recalculate it every loop iteration. Furthermore, Once we've done that, it becomes clear that we don't actually need to calculate a padding size at all - by flipping the arithmetic around, we can just combine the upper limit, size, and mask directly to check against the lower limit. For an arm64 build, this alone knocks 16% off the size of the entire alloc_iova() function! Signed-off-by: Zhen Lei Tested-by: Ard Biesheuvel Tested-by: Zhen Lei [rm: simplified more of the arithmetic, rewrote commit message] Signed-off-by: Robin Murphy --- v2: No change drivers/iommu/iova.c | 40 ++++++++++++++-------------------------- 1 file changed, 14 insertions(+), 26 deletions(-) -- 2.12.2.dirty diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c index 8f7552dc4e04..d094d1ca8f23 100644 --- a/drivers/iommu/iova.c +++ b/drivers/iommu/iova.c @@ -129,16 +129,6 @@ iova_insert_rbtree(struct rb_root *root, struct iova *iova, rb_insert_color(&iova->node, root); } -/* - * Computes the padding size required, to make the start address - * naturally aligned on the power-of-two order of its size - */ -static unsigned int -iova_get_pad_size(unsigned int size, unsigned int limit_pfn) -{ - return (limit_pfn - size) & (__roundup_pow_of_two(size) - 1); -} - static int __alloc_and_insert_iova_range(struct iova_domain *iovad, unsigned long size, unsigned long limit_pfn, struct iova *new, bool size_aligned) @@ -146,7 +136,10 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, struct rb_node *prev, *curr = NULL; unsigned long flags; unsigned long saved_pfn; - unsigned int pad_size = 0; + unsigned long align_mask = ~0UL; + + if (size_aligned) + align_mask <<= __fls(size); /* Walk the tree backwards */ spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); @@ -156,31 +149,26 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, while (curr) { struct iova *curr_iova = rb_entry(curr, struct iova, node); - if (limit_pfn <= curr_iova->pfn_lo) { + if (limit_pfn <= curr_iova->pfn_lo) goto move_left; - } else if (limit_pfn > curr_iova->pfn_hi) { - if (size_aligned) - pad_size = iova_get_pad_size(size, limit_pfn); - if ((curr_iova->pfn_hi + size + pad_size) < limit_pfn) - break; /* found a free slot */ - } + + if (((limit_pfn - size) & align_mask) > curr_iova->pfn_hi) + break; /* found a free slot */ + limit_pfn = curr_iova->pfn_lo; move_left: prev = curr; curr = rb_prev(curr); } - if (!curr) { - if (size_aligned) - pad_size = iova_get_pad_size(size, limit_pfn); - if ((iovad->start_pfn + size + pad_size) > limit_pfn) { - spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); - return -ENOMEM; - } + if (limit_pfn < size || + (!curr && ((limit_pfn - size) & align_mask) < iovad->start_pfn)) { + spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); + return -ENOMEM; } /* pfn_lo will point to size aligned address if size_aligned is set */ - new->pfn_lo = limit_pfn - (size + pad_size); + new->pfn_lo = (limit_pfn - size) & align_mask; new->pfn_hi = new->pfn_lo + size - 1; /* If we have 'prev', it's a valid place to start the insertion. */