From patchwork Tue Jul 18 16:57:20 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Robin Murphy X-Patchwork-Id: 108160 Delivered-To: patch@linaro.org Received: by 10.182.45.195 with SMTP id p3csp6154191obm; Tue, 18 Jul 2017 10:04:33 -0700 (PDT) X-Received: by 10.99.171.1 with SMTP id p1mr2728324pgf.140.1500397473011; Tue, 18 Jul 2017 10:04:33 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1500397473; cv=none; d=google.com; s=arc-20160816; b=bXYekigjaTOle3rkz6GKq3x+QeJEh5j00Do3oUIaA8LW+E8Y2mzNMJfbUiDyogLW1S 4ofz83SzKHP5OfMyj9Fr+rS4mbqGba60/arsmi/miCSQQJou/s20govdiaJwQDuG/JRR Zw/hqmymYMHoO9K/7ZAoHZ5+PwPpsm+a+/denUWA4MqOFHjiOaztw+YSZW7gITc8fxw0 lxmpq2eHLjD9sUTQf5yXB9A23YdGbnIQpsJ4Z84q/kDIUF2Gs8ZvTUe8qrleu7WBCpf5 UD72L/zy3C2ps11stcLfKd92pFeDSBcCu+bKKv1s6u944cSmj+RK98vkonrcTim4hbN3 1y5Q== 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=rGSPFaegLDKWAZxMiwJ9RLMJeIYweMyvI9C8CLgRN+k=; b=R/Y+aEBIp2ns3jqN9NP20NNT1P7R+6VIypHEb2KJyTiPP+v4Y/AA1bc14ecRjKUTMO NbyGYPXiqQEYia7589aiynze2KBuUJ/epCdcM058vrQhUg4W6HZ0M1vxcq0qyRZIvFye KgkRaniE4iu0UAdQt3poRzzuBycg3jVUDtWFWdC1kqGRiQzrRDR93a51ungWXtPtT+7K JRn0EQTL8y7VTGoshGdTrlqSoYXGP30UmMlpiqRm2896XXybwlg0/bcQark4bdXo9FDL UFHfSfm5KdZlUyHLU4T8Cj0HMAE37qyBDqvqiY+1xJlJuu2Qet+nYRx4MZfIjdDIbvvR /lBA== 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 d9si2154321pfd.54.2017.07.18.10.04.32; Tue, 18 Jul 2017 10:04:32 -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 S1752697AbdGRREa (ORCPT + 25 others); Tue, 18 Jul 2017 13:04:30 -0400 Received: from foss.arm.com ([217.140.101.70]:56204 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752290AbdGRRAU (ORCPT ); Tue, 18 Jul 2017 13:00:20 -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 4BD5F15B2; Tue, 18 Jul 2017 10:00:20 -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 7F0A03F577; Tue, 18 Jul 2017 10:00:18 -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 2/4] iommu/iova: Optimise the padding calculation Date: Tue, 18 Jul 2017 17:57:20 +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 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 [rm: simplified more of the arithmetic, rewrote commit message] Signed-off-by: Robin Murphy --- 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. */