From patchwork Tue Aug 22 15:17:43 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Robin Murphy X-Patchwork-Id: 110688 Delivered-To: patch@linaro.org Received: by 10.140.95.78 with SMTP id h72csp2829467qge; Tue, 22 Aug 2017 08:18:40 -0700 (PDT) X-Received: by 10.99.115.93 with SMTP id d29mr1100599pgn.364.1503415120841; Tue, 22 Aug 2017 08:18:40 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1503415120; cv=none; d=google.com; s=arc-20160816; b=rNZ1OKMVgzYMh6U7Dpkr1uIOphf7WcXLW+j+PztSDHmKVp1v/3PaONp9QLkpjKbfhf G+DYApE9sc51xsJq7L9r+5X/3InEJflTaV49AkM3ofl0OgIUow8a8RQOXJfAet93E2H1 jxMBQrs8sDRt62nNuBMa+Hkc7RsfOd6mUD+Hk+VJeMkSUSe36Nt/MWjH7RCjyxleF1re 7xNLCqNUXbqzsaiOJ1M6S4SU2hxmqeXi8+cCKZ37kHv8aT1BlbjRP/N+P23ZPrGMs8Jd Un7vmOV0BggdKeFxOGuB/Fde9fP2u/sMZmyJ9DQOFl7a57Pr2P0ErBIiQLtWctUubNrw 18Qw== 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=KLqA6DQRYq9vuuMlLlVF/MncbEfz0m5uEghkgzmu8Dk=; b=M0rJWaQh5nb853v5VqWBuxMboyYxlYMMwa+OD15AyllefT3MMzL7GkWVw98TKQ/1WG KZ6vf7uQfS4XrO3CXzXZXHF140ay9jfcxCXTa+Qy1srnP+bVWnPCzYTvBXBKy6QmBrEH qFuDweTk1ZZOOWyw2+DVXvTuAHMVU6M3+3JLMUAk3O8GEDpHw0HeVE40SAYoVKHP0E9O b5uYW0/H1uWPwn81Eeu9Ce6piui+2uDH/ee0UN37Ju5XpRgHD293pkqdNxVbdV/+JiEj qADxRhiMxPwpZYGDP4t+KuO67kYgtQlu12g+HxBvTha2GDrEK9XH7xesjMLPXO3TEdEZ OAqw== 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 a65si8939485pli.624.2017.08.22.08.18.40; Tue, 22 Aug 2017 08:18:40 -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 S933194AbdHVPSi (ORCPT + 26 others); Tue, 22 Aug 2017 11:18:38 -0400 Received: from foss.arm.com ([217.140.101.70]:45432 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932989AbdHVPR4 (ORCPT ); Tue, 22 Aug 2017 11:17:56 -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 30D7815AD; Tue, 22 Aug 2017 08:17:56 -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 CF3793F577; Tue, 22 Aug 2017 08:17:54 -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 2/4] iommu/iova: Optimise the padding calculation Date: Tue, 22 Aug 2017 16:17:43 +0100 Message-Id: <27abf39c80518a2ce4c98048577ec803ebfd8423.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 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 --- v3: No change drivers/iommu/iova.c | 40 ++++++++++++++-------------------------- 1 file changed, 14 insertions(+), 26 deletions(-) -- 2.13.4.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. */