iommu.lists.linux-foundation.org archive mirror
 help / color / mirror / Atom feed
From: Robin Murphy <robin.murphy@arm.com>
To: vjitta@codeaurora.org, joro@8bytes.org,
	iommu@lists.linux-foundation.org,  linux-kernel@vger.kernel.org
Cc: vinmenon@codeaurora.org, kernel-team@android.com
Subject: Re: [PATCH v2 1/2] iommu/iova: Retry from last rb tree node if iova search fails
Date: Fri, 18 Sep 2020 15:18:04 +0100	[thread overview]
Message-ID: <07270e29-c9d4-ae8c-a236-eb6fefccbf6c@arm.com> (raw)
In-Reply-To: <1597927761-24441-1-git-send-email-vjitta@codeaurora.org>

On 2020-08-20 13:49, vjitta@codeaurora.org wrote:
> From: Vijayanand Jitta <vjitta@codeaurora.org>
> 
> When ever a new iova alloc request comes iova is always searched
> from the cached node and the nodes which are previous to cached
> node. So, even if there is free iova space available in the nodes
> which are next to the cached node iova allocation can still fail
> because of this approach.
> 
> Consider the following sequence of iova alloc and frees on
> 1GB of iova space
> 
> 1) alloc - 500MB
> 2) alloc - 12MB
> 3) alloc - 499MB
> 4) free -  12MB which was allocated in step 2
> 5) alloc - 13MB
> 
> After the above sequence we will have 12MB of free iova space and
> cached node will be pointing to the iova pfn of last alloc of 13MB
> which will be the lowest iova pfn of that iova space. Now if we get an
> alloc request of 2MB we just search from cached node and then look
> for lower iova pfn's for free iova and as they aren't any, iova alloc
> fails though there is 12MB of free iova space.
> 
> To avoid such iova search failures do a retry from the last rb tree node
> when iova search fails, this will search the entire tree and get an iova
> if its available.
> 
> Signed-off-by: Vijayanand Jitta <vjitta@codeaurora.org>
> ---
>   drivers/iommu/iova.c | 23 +++++++++++++++++------
>   1 file changed, 17 insertions(+), 6 deletions(-)
> 
> diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> index 49fc01f..4e77116 100644
> --- a/drivers/iommu/iova.c
> +++ b/drivers/iommu/iova.c
> @@ -184,8 +184,9 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
>   	struct rb_node *curr, *prev;
>   	struct iova *curr_iova;
>   	unsigned long flags;
> -	unsigned long new_pfn;
> +	unsigned long new_pfn, low_pfn_new;
>   	unsigned long align_mask = ~0UL;
> +	unsigned long high_pfn = limit_pfn, low_pfn = iovad->start_pfn;
>   
>   	if (size_aligned)
>   		align_mask <<= fls_long(size - 1);
> @@ -198,15 +199,25 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
>   
>   	curr = __get_cached_rbnode(iovad, limit_pfn);
>   	curr_iova = rb_entry(curr, struct iova, node);
> +	low_pfn_new = curr_iova->pfn_hi + 1;

Could we call "low_pfn_new" something like "retry_pfn" instead? This 
code already has unavoidable readability struggles with so many 
different "pfn"s in play, so having two different meanings of "new" 
really doesn't help.

Other than that, I think this looks OK (IIRC it's basically what I 
originally suggested), so with the naming tweaked,

Reviewed-by: Robin Murphy <robin.murphy@arm.com>

> +
> +retry:
>   	do {
> -		limit_pfn = min(limit_pfn, curr_iova->pfn_lo);
> -		new_pfn = (limit_pfn - size) & align_mask;
> +		high_pfn = min(high_pfn, curr_iova->pfn_lo);
> +		new_pfn = (high_pfn - size) & align_mask;
>   		prev = curr;
>   		curr = rb_prev(curr);
>   		curr_iova = rb_entry(curr, struct iova, node);
> -	} while (curr && new_pfn <= curr_iova->pfn_hi);
> -
> -	if (limit_pfn < size || new_pfn < iovad->start_pfn) {
> +	} while (curr && new_pfn <= curr_iova->pfn_hi && new_pfn >= low_pfn);
> +
> +	if (high_pfn < size || new_pfn < low_pfn) {
> +		if (low_pfn == iovad->start_pfn && low_pfn_new < limit_pfn) {
> +			high_pfn = limit_pfn;
> +			low_pfn = low_pfn_new;
> +			curr = &iovad->anchor.node;
> +			curr_iova = rb_entry(curr, struct iova, node);
> +			goto retry;
> +		}
>   		iovad->max32_alloc_size = size;
>   		goto iova32_full;
>   	}
> 
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

  parent reply	other threads:[~2020-09-18 14:18 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-08-20 12:49 vjitta
2020-08-20 12:49 ` [PATCH v2 2/2] iommu/iova: Free global iova rcache on iova alloc failure vjitta
2020-09-18 14:41   ` Robin Murphy
2020-09-28 12:41     ` Vijayanand Jitta
2020-09-30  5:59       ` Vijayanand Jitta
2020-08-28  7:31 ` [PATCH v2 1/2] iommu/iova: Retry from last rb tree node if iova search fails Vijayanand Jitta
2020-09-14  4:50   ` Vijayanand Jitta
2020-09-18  8:18     ` Joerg Roedel
2020-09-18 14:18 ` Robin Murphy [this message]
2020-09-30  5:48   ` Vijayanand Jitta

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=07270e29-c9d4-ae8c-a236-eb6fefccbf6c@arm.com \
    --to=robin.murphy@arm.com \
    --cc=iommu@lists.linux-foundation.org \
    --cc=joro@8bytes.org \
    --cc=kernel-team@android.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=vinmenon@codeaurora.org \
    --cc=vjitta@codeaurora.org \
    --subject='Re: [PATCH v2 1/2] iommu/iova: Retry from last rb tree node if iova search fails' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).