From: David Hildenbrand <david@redhat.com>
To: Uladzislau Rezki <urezki@gmail.com>
Cc: LKML <linux-kernel@vger.kernel.org>,
Ping Fang <pifang@redhat.com>,
Andrew Morton <akpm@linux-foundation.org>,
Roman Gushchin <guro@fb.com>, Michal Hocko <mhocko@suse.com>,
Oscar Salvador <osalvador@suse.de>,
Linux Memory Management List <linux-mm@kvack.org>
Subject: Re: [PATCH v1] mm/vmalloc: fix exact allocations with an alignment > 1
Date: Thu, 23 Sep 2021 19:42:55 +0200 [thread overview]
Message-ID: <437ff5c9-1b36-8ef7-1ce6-b3125e42de93@redhat.com> (raw)
In-Reply-To: <20210922104141.GA27011@pc638.lan>
On 22.09.21 12:41, Uladzislau Rezki wrote:
> On Wed, Sep 22, 2021 at 10:34:55AM +0200, David Hildenbrand wrote:
>>>> No, that's leaking implementation details to the caller. And no, increasing
>>>> the range and eventually allocating something bigger (e.g., placing a huge
>>>> page where it might not have been possible) is not acceptable for KASAN.
>>>>
>>>> If you're terribly unhappy with this patch,
>>> Sorry to say but it simple does not make sense.
>>>
>>
>> Let's agree to disagree.
>>
>> find_vmap_lowest_match() is imprecise now and that's an issue for exact
>> allocations. We can either make it fully precise again (eventually degrading
>> allocation performance) or just special-case exact allocations to fix the
>> regression.
>>
>> I decided to go the easy path and do the latter; I do agree that making
>> find_vmap_lowest_match() fully precise again might be preferred -- we could
>> have other allocations failing right now although there are still suitable
>> holes.
>>
>> I briefly thought about performing the search in find_vmap_lowest_match()
>> twice. First, start the search without an extended range, and fallback to
>> the extended range if that search fails. Unfortunately, I think that still
>> won't make the function completely precise due to the way we might miss
>> searching some suitable subtrees.
>>
>>>>
>>>> please suggest something reasonable to fix exact allocations:
>>>> a) Fixes the KASAN use case.
>>>> b) Allows for automatic placement of huge pages for exact allocations.
>>>> c) Doesn't leak implementation details into the caller.
>>>>
>>> I am looking at it.
>>
> I am testing this:
>
> <snip>
> diff --git a/mm/vmalloc.c b/mm/vmalloc.c
> index dcf23d16a308..cdf3bda6313d 100644
> --- a/mm/vmalloc.c
> +++ b/mm/vmalloc.c
> @@ -1161,18 +1161,14 @@ find_vmap_lowest_match(unsigned long size,
> {
> struct vmap_area *va;
> struct rb_node *node;
> - unsigned long length;
>
> /* Start from the root. */
> node = free_vmap_area_root.rb_node;
>
> - /* Adjust the search size for alignment overhead. */
> - length = size + align - 1;
> -
> while (node) {
> va = rb_entry(node, struct vmap_area, rb_node);
>
> - if (get_subtree_max_size(node->rb_left) >= length &&
> + if (get_subtree_max_size(node->rb_left) >= size &&
> vstart < va->va_start) {
> node = node->rb_left;
> } else {
> @@ -1182,9 +1178,9 @@ find_vmap_lowest_match(unsigned long size,
> /*
> * Does not make sense to go deeper towards the right
> * sub-tree if it does not have a free block that is
> - * equal or bigger to the requested search length.
> + * equal or bigger to the requested search size.
> */
> - if (get_subtree_max_size(node->rb_right) >= length) {
> + if (get_subtree_max_size(node->rb_right) >= size) {
> node = node->rb_right;
> continue;
> }
> @@ -1192,16 +1188,30 @@ find_vmap_lowest_match(unsigned long size,
> /*
> * OK. We roll back and find the first right sub-tree,
> * that will satisfy the search criteria. It can happen
> - * only once due to "vstart" restriction.
> + * due to "vstart" restriction or an alignment overhead.
> */
> while ((node = rb_parent(node))) {
> va = rb_entry(node, struct vmap_area, rb_node);
> if (is_within_this_va(va, size, align, vstart))
> return va;
>
> - if (get_subtree_max_size(node->rb_right) >= length &&
> + if (get_subtree_max_size(node->rb_right) >= size &&
> vstart <= va->va_start) {
> + /*
> + * Shift the vstart forward, so we do not loop over same
> + * sub-tree force and back. The aim is to continue tree
> + * scanning toward higher addresses cutting off previous
> + * ones.
> + *
> + * Please note we update vstart with parent's start address
> + * adding "1" because we do not want to enter same sub-tree
> + * one more time after it has already been inspected and no
> + * suitable free block found there.
> + */
> + vstart = va->va_start + 1;
> node = node->rb_right;
> +
> + /* Scan a sub-tree rooted at "node". */
> break;
> }
> }
> <snip>
>
> so it handles any alignment and is accurate when it comes to searching the most
> lowest free block when user wants to allocate with a special alignment value.
>
> Could you please help and test the KASAN use case?
Sure, I'll give it a spin tomorrow! Thanks!
--
Thanks,
David / dhildenb
next prev parent reply other threads:[~2021-09-23 17:43 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-09-08 13:27 [PATCH v1] mm/vmalloc: fix exact allocations with an alignment > 1 David Hildenbrand
2021-09-13 8:44 ` Uladzislau Rezki
2021-09-14 19:15 ` Uladzislau Rezki
2021-09-15 9:02 ` David Hildenbrand
2021-09-16 19:34 ` Uladzislau Rezki
2021-09-17 8:47 ` David Hildenbrand
2021-09-21 22:13 ` Uladzislau Rezki
2021-09-22 8:34 ` David Hildenbrand
2021-09-22 10:41 ` Uladzislau Rezki
2021-09-23 17:42 ` David Hildenbrand [this message]
2021-09-24 12:42 ` David Hildenbrand
2021-09-29 14:30 ` Uladzislau Rezki
2021-09-29 14:40 ` David Hildenbrand
2021-09-29 14:49 ` Uladzislau Rezki
2021-09-29 15:05 ` David Hildenbrand
2021-09-29 16:08 ` Uladzislau Rezki
2021-09-29 16:10 ` David Hildenbrand
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=437ff5c9-1b36-8ef7-1ce6-b3125e42de93@redhat.com \
--to=david@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=guro@fb.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mhocko@suse.com \
--cc=osalvador@suse.de \
--cc=pifang@redhat.com \
--cc=urezki@gmail.com \
/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).