From: Robin Murphy <robin.murphy@arm.com>
To: John Garry <john.garry@huawei.com>, joro@8bytes.org
Cc: vjitta@codeaurora.org, iommu@lists.linux-foundation.org,
Linuxarm <linuxarm@huawei.com>,
linux-kernel@vger.kernel.org
Subject: Re: [PATCH 2/2] iommu/iova: Improve restart logic
Date: Thu, 18 Mar 2021 13:20:03 +0000 [thread overview]
Message-ID: <878f4f77-97ee-898d-eb05-4548cf00ec27@arm.com> (raw)
In-Reply-To: <6cea11f9-e98d-98cb-6789-93abd8833fa0@huawei.com>
On 2021-03-18 11:38, John Garry wrote:
> On 10/03/2021 17:47, John Garry wrote:
>> On 09/03/2021 15:55, John Garry wrote:
>>> On 05/03/2021 16:35, Robin Murphy wrote:
>>>
>>> Hi Robin,
>>>
>>>> When restarting after searching below the cached node fails, resetting
>>>> the start point to the anchor node is often overly pessimistic. If
>>>> allocations are made with mixed limits - particularly in the case of
>>>> the
>>>> opportunistic 32-bit allocation for PCI devices - this could mean
>>>> significant time wasted walking through the whole populated upper range
>>>> just to reach the initial limit.
>>>
>>> Right
>>>
>>>> We can improve on that by implementing
>>>> a proper tree traversal to find the first node above the relevant
>>>> limit,
>>>> and set the exact start point.
>>>
>>> Thanks for this. However, as mentioned in the other thread, this does
>>> not help our performance regression Re: commit 4e89dce72521.
>>>
>>> And mentioning this "retry" approach again, in case it was missed,
>>> from my experiment on the affected HW, it also has generally a
>>> dreadfully low success rate - less than 1% for the 32b range retry.
>>> Retry rate is about 20%. So I am saying from this 20%, less than 1%
>>> of those succeed.
Well yeah, in your particular case you're allocating from a heavily
over-contended address space, so much of the time it is genuinely full.
Plus you're primarily churning one or two sizes of IOVA, so there's a
high chance that you will either allocate immediately from the cached
node (after a previous free), or search the whole space and fail. In
case it was missed, searching only some arbitrary subset of the space
before giving up is not a good behaviour for an allocator to have in
general.
>> So since the retry means that we search through the complete pfn range
>> most of the time (due to poor success rate), we should be able to do a
>> better job at maintaining an accurate max alloc size, by calculating
>> it from the range search, and not relying on max alloc failed or
>> resetting it frequently. Hopefully that would mean that we're smarter
>> about not trying the allocation.
>
> So I tried that out and we seem to be able to scrap back an appreciable
> amount of performance. Maybe 80% of original, with with another change,
> below.
TBH if you really want to make allocation more efficient I think there
are more radical changes that would be worth experimenting with, like
using some form of augmented rbtree to also encode the amount of free
space under each branch, or representing the free space in its own
parallel tree, or whether some other structure entirely might be a
better bet these days.
And if you just want to make your thing acceptably fast, now I'm going
to say stick a quirk somewhere to force the "forcedac" option on your
platform ;)
[...]
>>>> @@ -219,7 +256,7 @@ static int __alloc_and_insert_iova_range(struct
>>>> iova_domain *iovad,
>>>> if (low_pfn == iovad->start_pfn && retry_pfn < limit_pfn) {
>>>> high_pfn = limit_pfn;
>>>> low_pfn = retry_pfn;
>>>> - curr = &iovad->anchor.node;
>>>> + curr = iova_find_limit(iovad, limit_pfn);
>
>
> I see that it is now applied. However, alternatively could we just add a
> zero-length 32b boundary marker node for the 32b pfn restart point?
That would need special cases all over the place to prevent the marker
getting merged into reservations or hit by lookups, and at worst break
the ordering of the tree if a legitimate node straddles the boundary. I
did consider having the insert/delete routines keep track of yet another
cached node for whatever's currently the first thing above the 32-bit
boundary, but I was worried that might be a bit too invasive.
FWIW I'm currently planning to come back to this again when I have a bit
more time, since the optimum thing to do (modulo replacing the entire
algorithm...) is actually to make the second part of the search
*upwards* from the cached node to the limit. Furthermore, to revive my
arch/arm conversion I think we're realistically going to need a
compatibility option for bottom-up allocation to avoid too many nasty
surprises, so I'd like to generalise things to tackle both concerns at once.
Thanks,
Robin.
next prev parent reply other threads:[~2021-03-18 13:21 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-03-05 16:35 [PATCH 1/2] iommu/iova: Add rbtree entry helper Robin Murphy
2021-03-05 16:35 ` [PATCH 2/2] iommu/iova: Improve restart logic Robin Murphy
2021-03-09 15:55 ` John Garry
[not found] ` <d8e80756-a628-3a0d-77ac-1e9df734f1c5@huawei.com>
2021-03-18 11:38 ` John Garry
2021-03-18 13:20 ` Robin Murphy [this message]
2021-03-18 16:07 ` John Garry
2021-03-18 10:01 ` [PATCH 1/2] iommu/iova: Add rbtree entry helper Joerg Roedel
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=878f4f77-97ee-898d-eb05-4548cf00ec27@arm.com \
--to=robin.murphy@arm.com \
--cc=iommu@lists.linux-foundation.org \
--cc=john.garry@huawei.com \
--cc=joro@8bytes.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linuxarm@huawei.com \
--cc=vjitta@codeaurora.org \
/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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).