[v2,14/16] maple_tree: Refine mas_preallocate() node calculations

  Calculate the number of nodes based on the pending write action instead
of assuming the worst case.

This addresses a performance regression introduced in platforms that
have longer allocation timing.

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 48 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 47 insertions(+), 1 deletion(-)
  

On 6/12/23 22:39, Liam R. Howlett wrote:
> Calculate the number of nodes based on the pending write action instead
> of assuming the worst case.

Liam already gave me a heads-up on this patch, which I already replied 
to [1].

However, I think it might make sense to also reply to this patch directly.

For a mas_preallocate() calculating the actual required nodes to be 
allocated instead of assuming the worst to work, it is required to 
ensure that the tree does not change between calling mas_preallocate() 
and mas_store_prealloc() if my understanding is correct.

In DRM however, more specifically the DRM GPUVA Manager [2], we do have 
the case that we are not able to ensure this:

Jobs to create GPU mappings can be submitted by userspace, are queued up 
by the kernel and are processed asynchronously in dma-fence signalling 
critical paths, e.g. by using the drm_gpu_scheduler. Hence, we must be 
able to allocate the worst case amount of node, since at the time a job 
is submitted we can't predict the state the maple tree keeping track of 
mappings has once a mapping is inserted in the (asynchronous) dma-fence 
signalling critical path.

A more detailed explanation can be found in [1].

Could we keep a separate function for allocating the worst case amount 
of nodes additionally to this optimization? E.g. something like 
mas_preallocate_worst_case() or mas_preallocate_unlocked() (since I 
guess the new one requires the maple tree to be kept locked in order not 
to change)?

[1] 
https://lore.kernel.org/nouveau/68cd25de-e767-725e-2e7b-703217230bb0@redhat.com/T/#ma326e200b1de1e3c9df4e9fcb3bf243061fee8b5

[2] 
https://lore.kernel.org/linux-mm/20230620004217.4700-8-dakr@redhat.com/T/#m47ab82310f87793d0f0cc1825a316eb30ad5b653

- Danilo

> 
> This addresses a performance regression introduced in platforms that
> have longer allocation timing.
> 
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> ---
>   lib/maple_tree.c | 48 +++++++++++++++++++++++++++++++++++++++++++++++-
>   1 file changed, 47 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 048d6413a114..7ac5b5457603 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5541,9 +5541,55 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
>    */
>   int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>   {
> +	MA_WR_STATE(wr_mas, mas, entry);
> +	unsigned char node_size;
> +	int request = 1;
>   	int ret;
>   
> -	mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
> +
> +	if (unlikely(!mas->index && mas->last == ULONG_MAX))
> +		goto ask_now;
> +
> +	mas_wr_store_setup(&wr_mas);
> +	wr_mas.content = mas_start(mas);
> +	/* Root expand */
> +	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
> +		goto ask_now;
> +
> +	if (unlikely(!mas_wr_walk(&wr_mas))) {
> +		/* Spanning store, use worst case for now */
> +		request = 1 + mas_mt_height(mas) * 3;
> +		goto ask_now;
> +	}
> +
> +	/* At this point, we are at the leaf node that needs to be altered. */
> +	/* Exact fit, no nodes needed. */
> +	if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
> +		return 0;
> +
> +	mas_wr_end_piv(&wr_mas);
> +	node_size = mas_wr_new_end(&wr_mas);
> +	/* Slot store can avoid using any nodes */
> +	if (node_size == wr_mas.node_end && wr_mas.offset_end - mas->offset == 1)
> +		return 0;
> +
> +	if (node_size >= mt_slots[wr_mas.type]) {
> +		/* Split, worst case for now. */
> +		request = 1 + mas_mt_height(mas) * 2;
> +		goto ask_now;
> +	}
> +
> +	/* Appending does not need any nodes */
> +	if (node_size == wr_mas.node_end + 1 && mas->offset == wr_mas.node_end)
> +		return 0;
> +
> +	/* Potential spanning rebalance collapsing a node, use worst-case */
> +	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
> +		request = mas_mt_height(mas) * 2 - 1;
> +
> +	/* node store needs one node */
> +ask_now:
> +	mas_node_count_gfp(mas, request, gfp);
>   	mas->mas_flags |= MA_STATE_PREALLOC;
>   	if (likely(!mas_is_err(mas)))
>   		return 0;
  

在 2023/6/23 00:41, Danilo Krummrich 写道:
> On 6/12/23 22:39, Liam R. Howlett wrote:
>> Calculate the number of nodes based on the pending write action instead
>> of assuming the worst case.
> 
> Liam already gave me a heads-up on this patch, which I already replied 
> to [1].
> 
> However, I think it might make sense to also reply to this patch directly.
> 
> For a mas_preallocate() calculating the actual required nodes to be 
> allocated instead of assuming the worst to work, it is required to 
> ensure that the tree does not change between calling mas_preallocate() 
> and mas_store_prealloc() if my understanding is correct.
> 
> In DRM however, more specifically the DRM GPUVA Manager [2], we do have 
> the case that we are not able to ensure this:
> 
> Jobs to create GPU mappings can be submitted by userspace, are queued up 
> by the kernel and are processed asynchronously in dma-fence signalling 
> critical paths, e.g. by using the drm_gpu_scheduler. Hence, we must be 
> able to allocate the worst case amount of node, since at the time a job 
> is submitted we can't predict the state the maple tree keeping track of 
> mappings has once a mapping is inserted in the (asynchronous) dma-fence 
> signalling critical path.
> 
> A more detailed explanation can be found in [1].
> 
> Could we keep a separate function for allocating the worst case amount 
> of nodes additionally to this optimization? E.g. something like 
> mas_preallocate_worst_case() or mas_preallocate_unlocked() (since I 
> guess the new one requires the maple tree to be kept locked in order not 
> to change)?
Hi Danilo,

Your understanding seems incorrect. Even with previously unoptimized
mas_preallocate(), the maple tree cannot be modified between calls to
mas_preallocate() and mas_store_prealloc(). The calculation of the
number of pre-allocated nodes depends on the structure of the maple
tree. In the unoptimized mas_preallocate(), it depends on the height of
the tree. If the maple tree is modified before mas_store_prealloc() and
the height of the tree changes, the number of pre-allocated nodes is
inaccurate.

Regards,
Peng

> 
> [1] 
> https://lore.kernel.org/nouveau/68cd25de-e767-725e-2e7b-703217230bb0@redhat.com/T/#ma326e200b1de1e3c9df4e9fcb3bf243061fee8b5
> 
> [2] 
> https://lore.kernel.org/linux-mm/20230620004217.4700-8-dakr@redhat.com/T/#m47ab82310f87793d0f0cc1825a316eb30ad5b653
> 
> - Danilo
> 
>>
>> This addresses a performance regression introduced in platforms that
>> have longer allocation timing.
>>
>> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
>> ---
>>   lib/maple_tree.c | 48 +++++++++++++++++++++++++++++++++++++++++++++++-
>>   1 file changed, 47 insertions(+), 1 deletion(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 048d6413a114..7ac5b5457603 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -5541,9 +5541,55 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
>>    */
>>   int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>>   {
>> +    MA_WR_STATE(wr_mas, mas, entry);
>> +    unsigned char node_size;
>> +    int request = 1;
>>       int ret;
>> -    mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
>> +
>> +    if (unlikely(!mas->index && mas->last == ULONG_MAX))
>> +        goto ask_now;
>> +
>> +    mas_wr_store_setup(&wr_mas);
>> +    wr_mas.content = mas_start(mas);
>> +    /* Root expand */
>> +    if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
>> +        goto ask_now;
>> +
>> +    if (unlikely(!mas_wr_walk(&wr_mas))) {
>> +        /* Spanning store, use worst case for now */
>> +        request = 1 + mas_mt_height(mas) * 3;
>> +        goto ask_now;
>> +    }
>> +
>> +    /* At this point, we are at the leaf node that needs to be 
>> altered. */
>> +    /* Exact fit, no nodes needed. */
>> +    if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
>> +        return 0;
>> +
>> +    mas_wr_end_piv(&wr_mas);
>> +    node_size = mas_wr_new_end(&wr_mas);
>> +    /* Slot store can avoid using any nodes */
>> +    if (node_size == wr_mas.node_end && wr_mas.offset_end - 
>> mas->offset == 1)
>> +        return 0;
>> +
>> +    if (node_size >= mt_slots[wr_mas.type]) {
>> +        /* Split, worst case for now. */
>> +        request = 1 + mas_mt_height(mas) * 2;
>> +        goto ask_now;
>> +    }
>> +
>> +    /* Appending does not need any nodes */
>> +    if (node_size == wr_mas.node_end + 1 && mas->offset == 
>> wr_mas.node_end)
>> +        return 0;
>> +
>> +    /* Potential spanning rebalance collapsing a node, use worst-case */
>> +    if (node_size  - 1 <= mt_min_slots[wr_mas.type])
>> +        request = mas_mt_height(mas) * 2 - 1;
>> +
>> +    /* node store needs one node */
>> +ask_now:
>> +    mas_node_count_gfp(mas, request, gfp);
>>       mas->mas_flags |= MA_STATE_PREALLOC;
>>       if (likely(!mas_is_err(mas)))
>>           return 0;
> 
>
  

Hi Peng,

On 6/25/23 05:28, Peng Zhang wrote:
> 
> 
> 在 2023/6/23 00:41, Danilo Krummrich 写道:
>> On 6/12/23 22:39, Liam R. Howlett wrote:
>>> Calculate the number of nodes based on the pending write action instead
>>> of assuming the worst case.
>>
>> Liam already gave me a heads-up on this patch, which I already replied 
>> to [1].
>>
>> However, I think it might make sense to also reply to this patch 
>> directly.
>>
>> For a mas_preallocate() calculating the actual required nodes to be 
>> allocated instead of assuming the worst to work, it is required to 
>> ensure that the tree does not change between calling mas_preallocate() 
>> and mas_store_prealloc() if my understanding is correct.
>>
>> In DRM however, more specifically the DRM GPUVA Manager [2], we do 
>> have the case that we are not able to ensure this:
>>
>> Jobs to create GPU mappings can be submitted by userspace, are queued 
>> up by the kernel and are processed asynchronously in dma-fence 
>> signalling critical paths, e.g. by using the drm_gpu_scheduler. Hence, 
>> we must be able to allocate the worst case amount of node, since at 
>> the time a job is submitted we can't predict the state the maple tree 
>> keeping track of mappings has once a mapping is inserted in the 
>> (asynchronous) dma-fence signalling critical path.
>>
>> A more detailed explanation can be found in [1].
>>
>> Could we keep a separate function for allocating the worst case amount 
>> of nodes additionally to this optimization? E.g. something like 
>> mas_preallocate_worst_case() or mas_preallocate_unlocked() (since I 
>> guess the new one requires the maple tree to be kept locked in order 
>> not to change)?
> Hi Danilo,
> 
> Your understanding seems incorrect. Even with previously unoptimized
> mas_preallocate(), the maple tree cannot be modified between calls to
> mas_preallocate() and mas_store_prealloc(). The calculation of the
> number of pre-allocated nodes depends on the structure of the maple
> tree. In the unoptimized mas_preallocate(), it depends on the height of
> the tree. If the maple tree is modified before mas_store_prealloc() and
> the height of the tree changes, the number of pre-allocated nodes is
> inaccurate.

Thanks for pointing this out!

First of all, it's probably fair to say "naive me", it totally makes 
sense the tree height is needed - it's a b-tree.

On the other hand, unless I miss something (and if so, please let me 
know), something is bogus with the API then.

While the documentation of the Advanced API of the maple tree explicitly 
claims that the user of the API is responsible for locking, this should 
be limited to the bounds set by the maple tree implementation. Which 
means, the user must decide for either the internal (spin-) lock or an 
external lock (which possibly goes away in the future) and acquire and 
release it according to the rules maple tree enforces through lockdep 
checks.

Let's say one picks the internal lock. How is one supposed to ensure the 
tree isn't modified using the internal lock with mas_preallocate()?

Besides that, I think the documentation should definitely mention this 
limitation and give some guidance for the locking.

Currently, from an API perspective, I can't see how anyone not familiar 
with the implementation details would be able to recognize this limitation.

In terms of the GPUVA manager, unfortunately, it seems like I need to 
drop the maple tree and go back to using a rb-tree, since it seems there 
is no sane way doing a worst-case pre-allocation that does not suffer 
from this limitation.

- Danilo

> 
> Regards,
> Peng
> 
>>
>> [1] 
>> https://lore.kernel.org/nouveau/68cd25de-e767-725e-2e7b-703217230bb0@redhat.com/T/#ma326e200b1de1e3c9df4e9fcb3bf243061fee8b5
>>
>> [2] 
>> https://lore.kernel.org/linux-mm/20230620004217.4700-8-dakr@redhat.com/T/#m47ab82310f87793d0f0cc1825a316eb30ad5b653
>>
>> - Danilo
>>
>>>
>>> This addresses a performance regression introduced in platforms that
>>> have longer allocation timing.
>>>
>>> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
>>> ---
>>>   lib/maple_tree.c | 48 +++++++++++++++++++++++++++++++++++++++++++++++-
>>>   1 file changed, 47 insertions(+), 1 deletion(-)
>>>
>>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>>> index 048d6413a114..7ac5b5457603 100644
>>> --- a/lib/maple_tree.c
>>> +++ b/lib/maple_tree.c
>>> @@ -5541,9 +5541,55 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
>>>    */
>>>   int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>>>   {
>>> +    MA_WR_STATE(wr_mas, mas, entry);
>>> +    unsigned char node_size;
>>> +    int request = 1;
>>>       int ret;
>>> -    mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
>>> +
>>> +    if (unlikely(!mas->index && mas->last == ULONG_MAX))
>>> +        goto ask_now;
>>> +
>>> +    mas_wr_store_setup(&wr_mas);
>>> +    wr_mas.content = mas_start(mas);
>>> +    /* Root expand */
>>> +    if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
>>> +        goto ask_now;
>>> +
>>> +    if (unlikely(!mas_wr_walk(&wr_mas))) {
>>> +        /* Spanning store, use worst case for now */
>>> +        request = 1 + mas_mt_height(mas) * 3;
>>> +        goto ask_now;
>>> +    }
>>> +
>>> +    /* At this point, we are at the leaf node that needs to be 
>>> altered. */
>>> +    /* Exact fit, no nodes needed. */
>>> +    if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
>>> +        return 0;
>>> +
>>> +    mas_wr_end_piv(&wr_mas);
>>> +    node_size = mas_wr_new_end(&wr_mas);
>>> +    /* Slot store can avoid using any nodes */
>>> +    if (node_size == wr_mas.node_end && wr_mas.offset_end - 
>>> mas->offset == 1)
>>> +        return 0;
>>> +
>>> +    if (node_size >= mt_slots[wr_mas.type]) {
>>> +        /* Split, worst case for now. */
>>> +        request = 1 + mas_mt_height(mas) * 2;
>>> +        goto ask_now;
>>> +    }
>>> +
>>> +    /* Appending does not need any nodes */
>>> +    if (node_size == wr_mas.node_end + 1 && mas->offset == 
>>> wr_mas.node_end)
>>> +        return 0;
>>> +
>>> +    /* Potential spanning rebalance collapsing a node, use 
>>> worst-case */
>>> +    if (node_size  - 1 <= mt_min_slots[wr_mas.type])
>>> +        request = mas_mt_height(mas) * 2 - 1;
>>> +
>>> +    /* node store needs one node */
>>> +ask_now:
>>> +    mas_node_count_gfp(mas, request, gfp);
>>>       mas->mas_flags |= MA_STATE_PREALLOC;
>>>       if (likely(!mas_is_err(mas)))
>>>           return 0;
>>
>>
>
  

On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
> On the other hand, unless I miss something (and if so, please let me know),
> something is bogus with the API then.
> 
> While the documentation of the Advanced API of the maple tree explicitly
> claims that the user of the API is responsible for locking, this should be
> limited to the bounds set by the maple tree implementation. Which means, the
> user must decide for either the internal (spin-) lock or an external lock
> (which possibly goes away in the future) and acquire and release it
> according to the rules maple tree enforces through lockdep checks.
> 
> Let's say one picks the internal lock. How is one supposed to ensure the
> tree isn't modified using the internal lock with mas_preallocate()?
> 
> Besides that, I think the documentation should definitely mention this
> limitation and give some guidance for the locking.
> 
> Currently, from an API perspective, I can't see how anyone not familiar with
> the implementation details would be able to recognize this limitation.
> 
> In terms of the GPUVA manager, unfortunately, it seems like I need to drop
> the maple tree and go back to using a rb-tree, since it seems there is no
> sane way doing a worst-case pre-allocation that does not suffer from this
> limitation.

I haven't been paying much attention here (too many other things going
on), but something's wrong.

First, you shouldn't need to preallocate.  Preallocation is only there
for really gnarly cases.  The way this is *supposed* to work is that
the store walks down to the leaf, attempts to insert into that leaf
and tries to allocate new nodes with __GFP_NOWAIT.  If that fails,
it drops the spinlock, allocates with the gfp flags you've specified,
then rewalks the tree to retry the store, this time with allocated
nodes in its back pocket so that the store will succeed.
  

在 2023/6/26 08:38, Danilo Krummrich 写道:
> Hi Peng,
> 
> On 6/25/23 05:28, Peng Zhang wrote:
>>
>>
>> 在 2023/6/23 00:41, Danilo Krummrich 写道:
>>> On 6/12/23 22:39, Liam R. Howlett wrote:
>>>> Calculate the number of nodes based on the pending write action instead
>>>> of assuming the worst case.
>>>
>>> Liam already gave me a heads-up on this patch, which I already 
>>> replied to [1].
>>>
>>> However, I think it might make sense to also reply to this patch 
>>> directly.
>>>
>>> For a mas_preallocate() calculating the actual required nodes to be 
>>> allocated instead of assuming the worst to work, it is required to 
>>> ensure that the tree does not change between calling 
>>> mas_preallocate() and mas_store_prealloc() if my understanding is 
>>> correct.
>>>
>>> In DRM however, more specifically the DRM GPUVA Manager [2], we do 
>>> have the case that we are not able to ensure this:
>>>
>>> Jobs to create GPU mappings can be submitted by userspace, are queued 
>>> up by the kernel and are processed asynchronously in dma-fence 
>>> signalling critical paths, e.g. by using the drm_gpu_scheduler. 
>>> Hence, we must be able to allocate the worst case amount of node, 
>>> since at the time a job is submitted we can't predict the state the 
>>> maple tree keeping track of mappings has once a mapping is inserted 
>>> in the (asynchronous) dma-fence signalling critical path.
>>>
>>> A more detailed explanation can be found in [1].
>>>
>>> Could we keep a separate function for allocating the worst case 
>>> amount of nodes additionally to this optimization? E.g. something 
>>> like mas_preallocate_worst_case() or mas_preallocate_unlocked() 
>>> (since I guess the new one requires the maple tree to be kept locked 
>>> in order not to change)?
>> Hi Danilo,
>>
>> Your understanding seems incorrect. Even with previously unoptimized
>> mas_preallocate(), the maple tree cannot be modified between calls to
>> mas_preallocate() and mas_store_prealloc(). The calculation of the
>> number of pre-allocated nodes depends on the structure of the maple
>> tree. In the unoptimized mas_preallocate(), it depends on the height of
>> the tree. If the maple tree is modified before mas_store_prealloc() and
>> the height of the tree changes, the number of pre-allocated nodes is
>> inaccurate.
> 
> Thanks for pointing this out!
> 
> First of all, it's probably fair to say "naive me", it totally makes 
> sense the tree height is needed - it's a b-tree.
> 
> On the other hand, unless I miss something (and if so, please let me 
> know), something is bogus with the API then.
> 
> While the documentation of the Advanced API of the maple tree explicitly 
> claims that the user of the API is responsible for locking, this should 
> be limited to the bounds set by the maple tree implementation. Which 
> means, the user must decide for either the internal (spin-) lock or an 
> external lock (which possibly goes away in the future) and acquire and 
> release it according to the rules maple tree enforces through lockdep 
> checks.
> 
> Let's say one picks the internal lock. How is one supposed to ensure the 
> tree isn't modified using the internal lock with mas_preallocate()?
> 
> Besides that, I think the documentation should definitely mention this 
> limitation and give some guidance for the locking.
Yes, the documentation of maple tree is not detailed and complete.
> 
> Currently, from an API perspective, I can't see how anyone not familiar 
> with the implementation details would be able to recognize this limitation.
> 
> In terms of the GPUVA manager, unfortunately, it seems like I need to 
> drop the maple tree and go back to using a rb-tree, since it seems there 
> is no sane way doing a worst-case pre-allocation that does not suffer 
> from this limitation.
I also think preallocation may not be necessary, and I agree with what
Matthew said. Preallocation should be used in some cases where
preallocation has to be used. If preallocation is used, but the number
of preallocated nodes is insufficient because the tree is modified
midway, GFP_NOWAIT will be used for memory allocation during the tree
modification process, and the user may not notice that more nodes are
not from preallocation.

> 
> - Danilo
> 
>>
>> Regards,
>> Peng
>>
>>>
>>> [1] 
>>> https://lore.kernel.org/nouveau/68cd25de-e767-725e-2e7b-703217230bb0@redhat.com/T/#ma326e200b1de1e3c9df4e9fcb3bf243061fee8b5
>>>
>>> [2] 
>>> https://lore.kernel.org/linux-mm/20230620004217.4700-8-dakr@redhat.com/T/#m47ab82310f87793d0f0cc1825a316eb30ad5b653
>>>
>>> - Danilo
>>>
>>>>
>>>> This addresses a performance regression introduced in platforms that
>>>> have longer allocation timing.
>>>>
>>>> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
>>>> ---
>>>>   lib/maple_tree.c | 48 
>>>> +++++++++++++++++++++++++++++++++++++++++++++++-
>>>>   1 file changed, 47 insertions(+), 1 deletion(-)
>>>>
>>>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>>>> index 048d6413a114..7ac5b5457603 100644
>>>> --- a/lib/maple_tree.c
>>>> +++ b/lib/maple_tree.c
>>>> @@ -5541,9 +5541,55 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
>>>>    */
>>>>   int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>>>>   {
>>>> +    MA_WR_STATE(wr_mas, mas, entry);
>>>> +    unsigned char node_size;
>>>> +    int request = 1;
>>>>       int ret;
>>>> -    mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
>>>> +
>>>> +    if (unlikely(!mas->index && mas->last == ULONG_MAX))
>>>> +        goto ask_now;
>>>> +
>>>> +    mas_wr_store_setup(&wr_mas);
>>>> +    wr_mas.content = mas_start(mas);
>>>> +    /* Root expand */
>>>> +    if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
>>>> +        goto ask_now;
>>>> +
>>>> +    if (unlikely(!mas_wr_walk(&wr_mas))) {
>>>> +        /* Spanning store, use worst case for now */
>>>> +        request = 1 + mas_mt_height(mas) * 3;
>>>> +        goto ask_now;
>>>> +    }
>>>> +
>>>> +    /* At this point, we are at the leaf node that needs to be 
>>>> altered. */
>>>> +    /* Exact fit, no nodes needed. */
>>>> +    if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
>>>> +        return 0;
>>>> +
>>>> +    mas_wr_end_piv(&wr_mas);
>>>> +    node_size = mas_wr_new_end(&wr_mas);
>>>> +    /* Slot store can avoid using any nodes */
>>>> +    if (node_size == wr_mas.node_end && wr_mas.offset_end - 
>>>> mas->offset == 1)
>>>> +        return 0;
>>>> +
>>>> +    if (node_size >= mt_slots[wr_mas.type]) {
>>>> +        /* Split, worst case for now. */
>>>> +        request = 1 + mas_mt_height(mas) * 2;
>>>> +        goto ask_now;
>>>> +    }
>>>> +
>>>> +    /* Appending does not need any nodes */
>>>> +    if (node_size == wr_mas.node_end + 1 && mas->offset == 
>>>> wr_mas.node_end)
>>>> +        return 0;
>>>> +
>>>> +    /* Potential spanning rebalance collapsing a node, use 
>>>> worst-case */
>>>> +    if (node_size  - 1 <= mt_min_slots[wr_mas.type])
>>>> +        request = mas_mt_height(mas) * 2 - 1;
>>>> +
>>>> +    /* node store needs one node */
>>>> +ask_now:
>>>> +    mas_node_count_gfp(mas, request, gfp);
>>>>       mas->mas_flags |= MA_STATE_PREALLOC;
>>>>       if (likely(!mas_is_err(mas)))
>>>>           return 0;
>>>
>>>
>>
>
  

On 6/26/23 15:19, Matthew Wilcox wrote:
> On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
>> On the other hand, unless I miss something (and if so, please let me know),
>> something is bogus with the API then.
>>
>> While the documentation of the Advanced API of the maple tree explicitly
>> claims that the user of the API is responsible for locking, this should be
>> limited to the bounds set by the maple tree implementation. Which means, the
>> user must decide for either the internal (spin-) lock or an external lock
>> (which possibly goes away in the future) and acquire and release it
>> according to the rules maple tree enforces through lockdep checks.
>>
>> Let's say one picks the internal lock. How is one supposed to ensure the
>> tree isn't modified using the internal lock with mas_preallocate()?
>>
>> Besides that, I think the documentation should definitely mention this
>> limitation and give some guidance for the locking.
>>
>> Currently, from an API perspective, I can't see how anyone not familiar with
>> the implementation details would be able to recognize this limitation.
>>
>> In terms of the GPUVA manager, unfortunately, it seems like I need to drop
>> the maple tree and go back to using a rb-tree, since it seems there is no
>> sane way doing a worst-case pre-allocation that does not suffer from this
>> limitation.
> 
> I haven't been paying much attention here (too many other things going
> on), but something's wrong.
> 
> First, you shouldn't need to preallocate.  Preallocation is only there

Unfortunately, I think we really have a case where we have to. Typically 
GPU mappings are created in a dma-fence signalling critical path and 
that is where such mappings need to be added to the maple tree. Hence, 
we can't do any sleeping allocations there.

> for really gnarly cases.  The way this is *supposed* to work is that
> the store walks down to the leaf, attempts to insert into that leaf
> and tries to allocate new nodes with __GFP_NOWAIT.  If that fails,
> it drops the spinlock, allocates with the gfp flags you've specified,
> then rewalks the tree to retry the store, this time with allocated
> nodes in its back pocket so that the store will succeed.

You are talking about mas_store_gfp() here, right? And I guess, if the 
tree has changed while the spinlock was dropped and even more nodes are 
needed it just retries until it succeeds?

But what about mas_preallocate()? What happens if the tree changed in 
between mas_preallocate() and mas_store_prealloc()? Does the latter one 
fall back to __GFP_NOWAIT in such a case? I guess not, since 
mas_store_prealloc() has a void return type, and __GFP_NOWAIT could fail 
as well.

So, how to use the internal spinlock for mas_preallocate() and 
mas_store_prealloc() to ensure the tree can't change?
  

On 6/26/23 16:08, Peng Zhang wrote:
> 
> 
> 在 2023/6/26 08:38, Danilo Krummrich 写道:
>> Hi Peng,
>>
>> On 6/25/23 05:28, Peng Zhang wrote:
>>>
>>>
>>> 在 2023/6/23 00:41, Danilo Krummrich 写道:
>>>> On 6/12/23 22:39, Liam R. Howlett wrote:
>>>>> Calculate the number of nodes based on the pending write action 
>>>>> instead
>>>>> of assuming the worst case.
>>>>
>>>> Liam already gave me a heads-up on this patch, which I already 
>>>> replied to [1].
>>>>
>>>> However, I think it might make sense to also reply to this patch 
>>>> directly.
>>>>
>>>> For a mas_preallocate() calculating the actual required nodes to be 
>>>> allocated instead of assuming the worst to work, it is required to 
>>>> ensure that the tree does not change between calling 
>>>> mas_preallocate() and mas_store_prealloc() if my understanding is 
>>>> correct.
>>>>
>>>> In DRM however, more specifically the DRM GPUVA Manager [2], we do 
>>>> have the case that we are not able to ensure this:
>>>>
>>>> Jobs to create GPU mappings can be submitted by userspace, are 
>>>> queued up by the kernel and are processed asynchronously in 
>>>> dma-fence signalling critical paths, e.g. by using the 
>>>> drm_gpu_scheduler. Hence, we must be able to allocate the worst case 
>>>> amount of node, since at the time a job is submitted we can't 
>>>> predict the state the maple tree keeping track of mappings has once 
>>>> a mapping is inserted in the (asynchronous) dma-fence signalling 
>>>> critical path.
>>>>
>>>> A more detailed explanation can be found in [1].
>>>>
>>>> Could we keep a separate function for allocating the worst case 
>>>> amount of nodes additionally to this optimization? E.g. something 
>>>> like mas_preallocate_worst_case() or mas_preallocate_unlocked() 
>>>> (since I guess the new one requires the maple tree to be kept locked 
>>>> in order not to change)?
>>> Hi Danilo,
>>>
>>> Your understanding seems incorrect. Even with previously unoptimized
>>> mas_preallocate(), the maple tree cannot be modified between calls to
>>> mas_preallocate() and mas_store_prealloc(). The calculation of the
>>> number of pre-allocated nodes depends on the structure of the maple
>>> tree. In the unoptimized mas_preallocate(), it depends on the height of
>>> the tree. If the maple tree is modified before mas_store_prealloc() and
>>> the height of the tree changes, the number of pre-allocated nodes is
>>> inaccurate.
>>
>> Thanks for pointing this out!
>>
>> First of all, it's probably fair to say "naive me", it totally makes 
>> sense the tree height is needed - it's a b-tree.
>>
>> On the other hand, unless I miss something (and if so, please let me 
>> know), something is bogus with the API then.
>>
>> While the documentation of the Advanced API of the maple tree 
>> explicitly claims that the user of the API is responsible for locking, 
>> this should be limited to the bounds set by the maple tree 
>> implementation. Which means, the user must decide for either the 
>> internal (spin-) lock or an external lock (which possibly goes away in 
>> the future) and acquire and release it according to the rules maple 
>> tree enforces through lockdep checks.
>>
>> Let's say one picks the internal lock. How is one supposed to ensure 
>> the tree isn't modified using the internal lock with mas_preallocate()?
>>
>> Besides that, I think the documentation should definitely mention this 
>> limitation and give some guidance for the locking.
> Yes, the documentation of maple tree is not detailed and complete.
>>
>> Currently, from an API perspective, I can't see how anyone not 
>> familiar with the implementation details would be able to recognize 
>> this limitation.
>>
>> In terms of the GPUVA manager, unfortunately, it seems like I need to 
>> drop the maple tree and go back to using a rb-tree, since it seems 
>> there is no sane way doing a worst-case pre-allocation that does not 
>> suffer from this limitation.
> I also think preallocation may not be necessary, and I agree with what
> Matthew said. Preallocation should be used in some cases where
> preallocation has to be used. If preallocation is used, but the number
> of preallocated nodes is insufficient because the tree is modified
> midway, GFP_NOWAIT will be used for memory allocation during the tree
> modification process, and the user may not notice that more nodes are
> not from preallocation.

Please see my reply to Matthew. :)

- Danilo

> 
>>
>> - Danilo
>>
>>>
>>> Regards,
>>> Peng
>>>
>>>>
>>>> [1] 
>>>> https://lore.kernel.org/nouveau/68cd25de-e767-725e-2e7b-703217230bb0@redhat.com/T/#ma326e200b1de1e3c9df4e9fcb3bf243061fee8b5
>>>>
>>>> [2] 
>>>> https://lore.kernel.org/linux-mm/20230620004217.4700-8-dakr@redhat.com/T/#m47ab82310f87793d0f0cc1825a316eb30ad5b653
>>>>
>>>> - Danilo
>>>>
>>>>>
>>>>> This addresses a performance regression introduced in platforms that
>>>>> have longer allocation timing.
>>>>>
>>>>> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
>>>>> ---
>>>>>   lib/maple_tree.c | 48 
>>>>> +++++++++++++++++++++++++++++++++++++++++++++++-
>>>>>   1 file changed, 47 insertions(+), 1 deletion(-)
>>>>>
>>>>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>>>>> index 048d6413a114..7ac5b5457603 100644
>>>>> --- a/lib/maple_tree.c
>>>>> +++ b/lib/maple_tree.c
>>>>> @@ -5541,9 +5541,55 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
>>>>>    */
>>>>>   int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>>>>>   {
>>>>> +    MA_WR_STATE(wr_mas, mas, entry);
>>>>> +    unsigned char node_size;
>>>>> +    int request = 1;
>>>>>       int ret;
>>>>> -    mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
>>>>> +
>>>>> +    if (unlikely(!mas->index && mas->last == ULONG_MAX))
>>>>> +        goto ask_now;
>>>>> +
>>>>> +    mas_wr_store_setup(&wr_mas);
>>>>> +    wr_mas.content = mas_start(mas);
>>>>> +    /* Root expand */
>>>>> +    if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
>>>>> +        goto ask_now;
>>>>> +
>>>>> +    if (unlikely(!mas_wr_walk(&wr_mas))) {
>>>>> +        /* Spanning store, use worst case for now */
>>>>> +        request = 1 + mas_mt_height(mas) * 3;
>>>>> +        goto ask_now;
>>>>> +    }
>>>>> +
>>>>> +    /* At this point, we are at the leaf node that needs to be 
>>>>> altered. */
>>>>> +    /* Exact fit, no nodes needed. */
>>>>> +    if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
>>>>> +        return 0;
>>>>> +
>>>>> +    mas_wr_end_piv(&wr_mas);
>>>>> +    node_size = mas_wr_new_end(&wr_mas);
>>>>> +    /* Slot store can avoid using any nodes */
>>>>> +    if (node_size == wr_mas.node_end && wr_mas.offset_end - 
>>>>> mas->offset == 1)
>>>>> +        return 0;
>>>>> +
>>>>> +    if (node_size >= mt_slots[wr_mas.type]) {
>>>>> +        /* Split, worst case for now. */
>>>>> +        request = 1 + mas_mt_height(mas) * 2;
>>>>> +        goto ask_now;
>>>>> +    }
>>>>> +
>>>>> +    /* Appending does not need any nodes */
>>>>> +    if (node_size == wr_mas.node_end + 1 && mas->offset == 
>>>>> wr_mas.node_end)
>>>>> +        return 0;
>>>>> +
>>>>> +    /* Potential spanning rebalance collapsing a node, use 
>>>>> worst-case */
>>>>> +    if (node_size  - 1 <= mt_min_slots[wr_mas.type])
>>>>> +        request = mas_mt_height(mas) * 2 - 1;
>>>>> +
>>>>> +    /* node store needs one node */
>>>>> +ask_now:
>>>>> +    mas_node_count_gfp(mas, request, gfp);
>>>>>       mas->mas_flags |= MA_STATE_PREALLOC;
>>>>>       if (likely(!mas_is_err(mas)))
>>>>>           return 0;
>>>>
>>>>
>>>
>>
>
  

在 2023/6/26 22:27, Danilo Krummrich 写道:
> On 6/26/23 15:19, Matthew Wilcox wrote:
>> On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
>>> On the other hand, unless I miss something (and if so, please let me 
>>> know),
>>> something is bogus with the API then.
>>>
>>> While the documentation of the Advanced API of the maple tree explicitly
>>> claims that the user of the API is responsible for locking, this 
>>> should be
>>> limited to the bounds set by the maple tree implementation. Which 
>>> means, the
>>> user must decide for either the internal (spin-) lock or an external 
>>> lock
>>> (which possibly goes away in the future) and acquire and release it
>>> according to the rules maple tree enforces through lockdep checks.
>>>
>>> Let's say one picks the internal lock. How is one supposed to ensure the
>>> tree isn't modified using the internal lock with mas_preallocate()?
>>>
>>> Besides that, I think the documentation should definitely mention this
>>> limitation and give some guidance for the locking.
>>>
>>> Currently, from an API perspective, I can't see how anyone not 
>>> familiar with
>>> the implementation details would be able to recognize this limitation.
>>>
>>> In terms of the GPUVA manager, unfortunately, it seems like I need to 
>>> drop
>>> the maple tree and go back to using a rb-tree, since it seems there 
>>> is no
>>> sane way doing a worst-case pre-allocation that does not suffer from 
>>> this
>>> limitation.
>>
>> I haven't been paying much attention here (too many other things going
>> on), but something's wrong.
>>
>> First, you shouldn't need to preallocate.  Preallocation is only there
> 
> Unfortunately, I think we really have a case where we have to. Typically 
> GPU mappings are created in a dma-fence signalling critical path and 
> that is where such mappings need to be added to the maple tree. Hence, 
> we can't do any sleeping allocations there.
> 
>> for really gnarly cases.  The way this is *supposed* to work is that
>> the store walks down to the leaf, attempts to insert into that leaf
>> and tries to allocate new nodes with __GFP_NOWAIT.  If that fails,
>> it drops the spinlock, allocates with the gfp flags you've specified,
>> then rewalks the tree to retry the store, this time with allocated
>> nodes in its back pocket so that the store will succeed.
> 
> You are talking about mas_store_gfp() here, right? And I guess, if the 
> tree has changed while the spinlock was dropped and even more nodes are 
> needed it just retries until it succeeds?
> 
> But what about mas_preallocate()? What happens if the tree changed in 
> between mas_preallocate() and mas_store_prealloc()? Does the latter one 
> fall back to __GFP_NOWAIT in such a case? I guess not, since 
> mas_store_prealloc() has a void return type, and __GFP_NOWAIT could fail 
> as well.
mas_store_prealloc() will fallback to __GFP_NOWAIT and issue a warning.
If __GFP_NOWAIT allocation fails, BUG_ON() in mas_store_prealloc() will
be triggered.

> 
> So, how to use the internal spinlock for mas_preallocate() and 
> mas_store_prealloc() to ensure the tree can't change?
>
  

On Mon, Jun 26, 2023 at 04:27:54PM +0200, Danilo Krummrich wrote:
> On 6/26/23 15:19, Matthew Wilcox wrote:
> > On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
> > > On the other hand, unless I miss something (and if so, please let me know),
> > > something is bogus with the API then.
> > > 
> > > While the documentation of the Advanced API of the maple tree explicitly
> > > claims that the user of the API is responsible for locking, this should be
> > > limited to the bounds set by the maple tree implementation. Which means, the
> > > user must decide for either the internal (spin-) lock or an external lock
> > > (which possibly goes away in the future) and acquire and release it
> > > according to the rules maple tree enforces through lockdep checks.
> > > 
> > > Let's say one picks the internal lock. How is one supposed to ensure the
> > > tree isn't modified using the internal lock with mas_preallocate()?
> > > 
> > > Besides that, I think the documentation should definitely mention this
> > > limitation and give some guidance for the locking.
> > > 
> > > Currently, from an API perspective, I can't see how anyone not familiar with
> > > the implementation details would be able to recognize this limitation.
> > > 
> > > In terms of the GPUVA manager, unfortunately, it seems like I need to drop
> > > the maple tree and go back to using a rb-tree, since it seems there is no
> > > sane way doing a worst-case pre-allocation that does not suffer from this
> > > limitation.
> > 
> > I haven't been paying much attention here (too many other things going
> > on), but something's wrong.
> > 
> > First, you shouldn't need to preallocate.  Preallocation is only there
> 
> Unfortunately, I think we really have a case where we have to. Typically GPU
> mappings are created in a dma-fence signalling critical path and that is
> where such mappings need to be added to the maple tree. Hence, we can't do
> any sleeping allocations there.

OK, so there are various ways to hadle this, depending on what's
appropriate for your case.

The simplest is to use GFP_ATOMIC.  Essentially, you're saying to the MM
layer "This is too hard, let me tap into the emergency reserves".  It's
mildly frowned upon, so let's see if we can do better.

If you know where the allocation needs to be stored, but want it to act as
NULL until the time is right, you can store a ZERO entry.  That will read
as NULL until you store to it.  A pure overwriting store will not cause
any memory allocation since all the implementation has to do is change
a pointer.  The XArray wraps this up nicely behind an xa_reserve() API.
As you're discovering, the Maple Tree API isn't fully baked yet.
  

On 6/26/23 16:49, Peng Zhang wrote:
> 
> 
> 在 2023/6/26 22:27, Danilo Krummrich 写道:
>> On 6/26/23 15:19, Matthew Wilcox wrote:
>>> On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
>>>> On the other hand, unless I miss something (and if so, please let me 
>>>> know),
>>>> something is bogus with the API then.
>>>>
>>>> While the documentation of the Advanced API of the maple tree 
>>>> explicitly
>>>> claims that the user of the API is responsible for locking, this 
>>>> should be
>>>> limited to the bounds set by the maple tree implementation. Which 
>>>> means, the
>>>> user must decide for either the internal (spin-) lock or an external 
>>>> lock
>>>> (which possibly goes away in the future) and acquire and release it
>>>> according to the rules maple tree enforces through lockdep checks.
>>>>
>>>> Let's say one picks the internal lock. How is one supposed to ensure 
>>>> the
>>>> tree isn't modified using the internal lock with mas_preallocate()?
>>>>
>>>> Besides that, I think the documentation should definitely mention this
>>>> limitation and give some guidance for the locking.
>>>>
>>>> Currently, from an API perspective, I can't see how anyone not 
>>>> familiar with
>>>> the implementation details would be able to recognize this limitation.
>>>>
>>>> In terms of the GPUVA manager, unfortunately, it seems like I need 
>>>> to drop
>>>> the maple tree and go back to using a rb-tree, since it seems there 
>>>> is no
>>>> sane way doing a worst-case pre-allocation that does not suffer from 
>>>> this
>>>> limitation.
>>>
>>> I haven't been paying much attention here (too many other things going
>>> on), but something's wrong.
>>>
>>> First, you shouldn't need to preallocate.  Preallocation is only there
>>
>> Unfortunately, I think we really have a case where we have to. 
>> Typically GPU mappings are created in a dma-fence signalling critical 
>> path and that is where such mappings need to be added to the maple 
>> tree. Hence, we can't do any sleeping allocations there.
>>
>>> for really gnarly cases.  The way this is *supposed* to work is that
>>> the store walks down to the leaf, attempts to insert into that leaf
>>> and tries to allocate new nodes with __GFP_NOWAIT.  If that fails,
>>> it drops the spinlock, allocates with the gfp flags you've specified,
>>> then rewalks the tree to retry the store, this time with allocated
>>> nodes in its back pocket so that the store will succeed.
>>
>> You are talking about mas_store_gfp() here, right? And I guess, if the 
>> tree has changed while the spinlock was dropped and even more nodes 
>> are needed it just retries until it succeeds?
>>
>> But what about mas_preallocate()? What happens if the tree changed in 
>> between mas_preallocate() and mas_store_prealloc()? Does the latter 
>> one fall back to __GFP_NOWAIT in such a case? I guess not, since 
>> mas_store_prealloc() has a void return type, and __GFP_NOWAIT could 
>> fail as well.
> mas_store_prealloc() will fallback to __GFP_NOWAIT and issue a warning.
> If __GFP_NOWAIT allocation fails, BUG_ON() in mas_store_prealloc() will
> be triggered.

Ok, so this is an absolute last resort and surely should not be relied on.

I think the maple tree should either strictly enforce (through locking 
policy) that this can never happen or if API wise it is OK not to lock 
these two is legit, return an error code rather then issue a warning and 
even worse call BUG_ON() in case it can't fix things up.

- Danilo

> 
>>
>> So, how to use the internal spinlock for mas_preallocate() and 
>> mas_store_prealloc() to ensure the tree can't change?
>>
>
  

On 6/26/23 16:52, Matthew Wilcox wrote:
> On Mon, Jun 26, 2023 at 04:27:54PM +0200, Danilo Krummrich wrote:
>> On 6/26/23 15:19, Matthew Wilcox wrote:
>>> On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
>>>> On the other hand, unless I miss something (and if so, please let me know),
>>>> something is bogus with the API then.
>>>>
>>>> While the documentation of the Advanced API of the maple tree explicitly
>>>> claims that the user of the API is responsible for locking, this should be
>>>> limited to the bounds set by the maple tree implementation. Which means, the
>>>> user must decide for either the internal (spin-) lock or an external lock
>>>> (which possibly goes away in the future) and acquire and release it
>>>> according to the rules maple tree enforces through lockdep checks.
>>>>
>>>> Let's say one picks the internal lock. How is one supposed to ensure the
>>>> tree isn't modified using the internal lock with mas_preallocate()?
>>>>
>>>> Besides that, I think the documentation should definitely mention this
>>>> limitation and give some guidance for the locking.
>>>>
>>>> Currently, from an API perspective, I can't see how anyone not familiar with
>>>> the implementation details would be able to recognize this limitation.
>>>>
>>>> In terms of the GPUVA manager, unfortunately, it seems like I need to drop
>>>> the maple tree and go back to using a rb-tree, since it seems there is no
>>>> sane way doing a worst-case pre-allocation that does not suffer from this
>>>> limitation.
>>>
>>> I haven't been paying much attention here (too many other things going
>>> on), but something's wrong.
>>>
>>> First, you shouldn't need to preallocate.  Preallocation is only there
>>
>> Unfortunately, I think we really have a case where we have to. Typically GPU
>> mappings are created in a dma-fence signalling critical path and that is
>> where such mappings need to be added to the maple tree. Hence, we can't do
>> any sleeping allocations there.
> 
> OK, so there are various ways to hadle this, depending on what's
> appropriate for your case.
> 
> The simplest is to use GFP_ATOMIC.  Essentially, you're saying to the MM
> layer "This is too hard, let me tap into the emergency reserves".  It's
> mildly frowned upon, so let's see if we can do better.
> 
> If you know where the allocation needs to be stored, but want it to act as
> NULL until the time is right, you can store a ZERO entry.  That will read
> as NULL until you store to it.  A pure overwriting store will not cause
> any memory allocation since all the implementation has to do is change
> a pointer.  The XArray wraps this up nicely behind an xa_reserve() API.
> As you're discovering, the Maple Tree API isn't fully baked yet.
> 

Unfortunately, GFP_ATOMIC seems the be the only option. I think storing 
entries in advance would not work. Typically userspace submits a job to 
the kernel issuing one or multiple requests to map and unmap memory in 
an ioctl. Such a job is then put into a queue and processed 
asynchronously in a dma-fence signalling critical section. Hence, at the 
we'd store entries in advance we could have an arbitrary amount of 
pending jobs potentially still messing with the same address space region.

So, the only way to go seems to be to use mas_store_gfp() with 
GFP_ATOMIC directly in the fence signalling critical path. I guess 
mas_store_gfp() does not BUG_ON() if it can't get atomic pages?

Also, I just saw that the tree is limited in it's height 
(MAPLE_HEIGHT_MAX). Do you think it could be a sane alternative to 
pre-allocate with MAPLE_HEIGHT_MAX rather than to rely on atomic pages? 
Or maybe a compromise of pre-allocating just a couple of nodes and then 
rely on atomic pages for the rest?

FYI, we're talking about a magnitude of hundreds of thousands of entries 
to be stored in the tree.

- Danilo
  

* Danilo Krummrich <dakr@redhat.com> [230626 14:37]:
> On 6/26/23 16:52, Matthew Wilcox wrote:
> > On Mon, Jun 26, 2023 at 04:27:54PM +0200, Danilo Krummrich wrote:
> > > On 6/26/23 15:19, Matthew Wilcox wrote:
> > > > On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
> > > > > On the other hand, unless I miss something (and if so, please let me know),
> > > > > something is bogus with the API then.
> > > > > 
> > > > > While the documentation of the Advanced API of the maple tree explicitly
> > > > > claims that the user of the API is responsible for locking, this should be
> > > > > limited to the bounds set by the maple tree implementation. Which means, the
> > > > > user must decide for either the internal (spin-) lock or an external lock
> > > > > (which possibly goes away in the future) and acquire and release it
> > > > > according to the rules maple tree enforces through lockdep checks.
> > > > > 
> > > > > Let's say one picks the internal lock. How is one supposed to ensure the
> > > > > tree isn't modified using the internal lock with mas_preallocate()?
> > > > > 
> > > > > Besides that, I think the documentation should definitely mention this
> > > > > limitation and give some guidance for the locking.
> > > > > 
> > > > > Currently, from an API perspective, I can't see how anyone not familiar with
> > > > > the implementation details would be able to recognize this limitation.
> > > > > 
> > > > > In terms of the GPUVA manager, unfortunately, it seems like I need to drop
> > > > > the maple tree and go back to using a rb-tree, since it seems there is no
> > > > > sane way doing a worst-case pre-allocation that does not suffer from this
> > > > > limitation.
> > > > 
> > > > I haven't been paying much attention here (too many other things going
> > > > on), but something's wrong.
> > > > 
> > > > First, you shouldn't need to preallocate.  Preallocation is only there
> > > 
> > > Unfortunately, I think we really have a case where we have to. Typically GPU
> > > mappings are created in a dma-fence signalling critical path and that is
> > > where such mappings need to be added to the maple tree. Hence, we can't do
> > > any sleeping allocations there.
> > 
> > OK, so there are various ways to hadle this, depending on what's
> > appropriate for your case.
> > 
> > The simplest is to use GFP_ATOMIC.  Essentially, you're saying to the MM
> > layer "This is too hard, let me tap into the emergency reserves".  It's
> > mildly frowned upon, so let's see if we can do better.
> > 
> > If you know where the allocation needs to be stored, but want it to act as
> > NULL until the time is right, you can store a ZERO entry.  That will read
> > as NULL until you store to it.  A pure overwriting store will not cause
> > any memory allocation since all the implementation has to do is change
> > a pointer.  The XArray wraps this up nicely behind an xa_reserve() API.
> > As you're discovering, the Maple Tree API isn't fully baked yet.
> > 
> 
> Unfortunately, GFP_ATOMIC seems the be the only option. I think storing
> entries in advance would not work. Typically userspace submits a job to the
> kernel issuing one or multiple requests to map and unmap memory in an ioctl.
> Such a job is then put into a queue and processed asynchronously in a
> dma-fence signalling critical section. Hence, at the we'd store entries in
> advance we could have an arbitrary amount of pending jobs potentially still
> messing with the same address space region.

What I think you are saying is that you have a number of requests
flooding in, which may overwrite the same areas, but are queued up to be
written after they are queued.  These operations look to be kept in
order according to the code in nouveau_job_submit[1].  Is this correct?

So then, your issue isn't that you don't know where they will land, but
don't know if the area that you reserved is already split into other
areas?  For instance, before the range 5-10 is backed by whatever
happens in the fence, it may have already become 5-6 & 8-10 by something
that came after (from userspace) but hasn't been processed by the
kernel that will live at 7?  So you can't write 5-10 right away because
you can't be sure 5-10 is going to exist once you reach the kernel fence
code that stores the entry?

Is my understanding of your issue correct?

Oh, and I guess the queued requests would have to remain ordered between
threads or whatever is on the other side?  I mean, you can't have two
threads firing different things into the kernel at the same region
because I would think the results would be unpredictable?

Can these overlapping entries partially overlap one region and another?
That is, can you have three in-flight writes that does something like:
store 1-10, store 10-20, store 5-15?

How stable of an output is needed?  Does each kernel write need to be
100% correct or is there a point where the userspace updates stop and
only then it is needed to be stable?

> 
> So, the only way to go seems to be to use mas_store_gfp() with GFP_ATOMIC
> directly in the fence signalling critical path. I guess mas_store_gfp() does
> not BUG_ON() if it can't get atomic pages?
> 
> Also, I just saw that the tree is limited in it's height (MAPLE_HEIGHT_MAX).
> Do you think it could be a sane alternative to pre-allocate with
> MAPLE_HEIGHT_MAX rather than to rely on atomic pages? Or maybe a compromise
> of pre-allocating just a couple of nodes and then rely on atomic pages for
> the rest?
> 
> FYI, we're talking about a magnitude of hundreds of thousands of entries to
> be stored in the tree.
> 

Since you are not tracking gaps, you will get 16 entries per node.  The
maximum height is 31, so that would be 16^31, assuming a gap between
each entry (the worst case), you can cut that in 1/2.  To assure you can
successfully allocate storage for a new entries, you'd need to allocate
30 * 3 + 1, or 91 nodes, which is 6 pages.  That'll be highly wasteful
as almost all of these would be freed, and sometimes all of them.

You estimate less than 1M entries, that would never go over 6 levels (8.3M
entries with the worst-case).  5 levels would get you 500K in the worst
case, but realistically you'll be in the 5 levels almost always.  So,
5*3+1 = 17 nodes, or 2 pages (1 node over 1 page).. assuming 4k pages.

[1] https://lore.kernel.org/linux-mm/20230620004217.4700-8-dakr@redhat.com/T/#Z2e.:..:20230620004217.4700-4-dakr::40redhat.com:1drivers:gpu:drm:drm_gem.c
  

Hi Liam,

On 6/27/23 03:58, Liam R. Howlett wrote:
> * Danilo Krummrich <dakr@redhat.com> [230626 14:37]:
>> On 6/26/23 16:52, Matthew Wilcox wrote:
>>> On Mon, Jun 26, 2023 at 04:27:54PM +0200, Danilo Krummrich wrote:
>>>> On 6/26/23 15:19, Matthew Wilcox wrote:
>>>>> On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
>>>>>> On the other hand, unless I miss something (and if so, please let me know),
>>>>>> something is bogus with the API then.
>>>>>>
>>>>>> While the documentation of the Advanced API of the maple tree explicitly
>>>>>> claims that the user of the API is responsible for locking, this should be
>>>>>> limited to the bounds set by the maple tree implementation. Which means, the
>>>>>> user must decide for either the internal (spin-) lock or an external lock
>>>>>> (which possibly goes away in the future) and acquire and release it
>>>>>> according to the rules maple tree enforces through lockdep checks.
>>>>>>
>>>>>> Let's say one picks the internal lock. How is one supposed to ensure the
>>>>>> tree isn't modified using the internal lock with mas_preallocate()?
>>>>>>
>>>>>> Besides that, I think the documentation should definitely mention this
>>>>>> limitation and give some guidance for the locking.
>>>>>>
>>>>>> Currently, from an API perspective, I can't see how anyone not familiar with
>>>>>> the implementation details would be able to recognize this limitation.
>>>>>>
>>>>>> In terms of the GPUVA manager, unfortunately, it seems like I need to drop
>>>>>> the maple tree and go back to using a rb-tree, since it seems there is no
>>>>>> sane way doing a worst-case pre-allocation that does not suffer from this
>>>>>> limitation.
>>>>>
>>>>> I haven't been paying much attention here (too many other things going
>>>>> on), but something's wrong.
>>>>>
>>>>> First, you shouldn't need to preallocate.  Preallocation is only there
>>>>
>>>> Unfortunately, I think we really have a case where we have to. Typically GPU
>>>> mappings are created in a dma-fence signalling critical path and that is
>>>> where such mappings need to be added to the maple tree. Hence, we can't do
>>>> any sleeping allocations there.
>>>
>>> OK, so there are various ways to hadle this, depending on what's
>>> appropriate for your case.
>>>
>>> The simplest is to use GFP_ATOMIC.  Essentially, you're saying to the MM
>>> layer "This is too hard, let me tap into the emergency reserves".  It's
>>> mildly frowned upon, so let's see if we can do better.
>>>
>>> If you know where the allocation needs to be stored, but want it to act as
>>> NULL until the time is right, you can store a ZERO entry.  That will read
>>> as NULL until you store to it.  A pure overwriting store will not cause
>>> any memory allocation since all the implementation has to do is change
>>> a pointer.  The XArray wraps this up nicely behind an xa_reserve() API.
>>> As you're discovering, the Maple Tree API isn't fully baked yet.
>>>
>>
>> Unfortunately, GFP_ATOMIC seems the be the only option. I think storing
>> entries in advance would not work. Typically userspace submits a job to the
>> kernel issuing one or multiple requests to map and unmap memory in an ioctl.
>> Such a job is then put into a queue and processed asynchronously in a
>> dma-fence signalling critical section. Hence, at the we'd store entries in
>> advance we could have an arbitrary amount of pending jobs potentially still
>> messing with the same address space region.
> 
> What I think you are saying is that you have a number of requests
> flooding in, which may overwrite the same areas, but are queued up to be
> written after they are queued.  These operations look to be kept in
> order according to the code in nouveau_job_submit[1].  Is this correct?

That's all correct.

(Although Nouveau isn't a good example in this case. Some aspects of it 
do and some aspects of it do not apply to the problem we're discussing 
here.)

> 
> So then, your issue isn't that you don't know where they will land, but
> don't know if the area that you reserved is already split into other
> areas?  For instance, before the range 5-10 is backed by whatever
> happens in the fence, it may have already become 5-6 & 8-10 by something
> that came after (from userspace) but hasn't been processed by the
> kernel that will live at 7?  So you can't write 5-10 right away because
> you can't be sure 5-10 is going to exist once you reach the kernel fence
> code that stores the entry?
> 
> Is my understanding of your issue correct?

Yes, it is.

However, the problem already starts while trying to reserve an area. In 
order to satisfy a user request, such a request is broken down into 
operations such as unmap mappings which are in the way entirely, remap 
mappings which intersect with the requested mapping and finally map the 
requested mapping. The execution of such a sequence must appear atomic 
and hence be locked accordingly. When trying to reserve an area we'd 
need to take that lock. But since this lock would be used in the 
dma-fence signalling critical path as well we'd not be allowed to do 
sleeping allocations while holding this lock.

Potentially, this could be solved with a retry loop though. Drop the 
lock while allocating, take it again and check whether we still got 
enough nodes allocated. Analogous to what the maple tree does in 
mas_store_gfp(), I guess.

> 
> Oh, and I guess the queued requests would have to remain ordered between
> threads or whatever is on the other side?  I mean, you can't have two
> threads firing different things into the kernel at the same region
> because I would think the results would be unpredictable?

Once a job is queued up in the kernel they remain ordered.

However, user threads could concurrently push jobs to the kernel 
altering the same region of the address space - it just would not make 
any sense for userspace to do that.

In general userspace is responsible for the semantics of the address 
space. The kernel basically just takes any (valid) request and make it 
happen. It also assures waiting and signalling of fences which might be 
bound to certain jobs and obviously keeps track of the VA space to be 
able to clean things up once a client disappears.

> 
> Can these overlapping entries partially overlap one region and another?
> That is, can you have three in-flight writes that does something like:
> store 1-10, store 10-20, store 5-15?

Absolutely, yes.

> 
> How stable of an output is needed?  Does each kernel write need to be
> 100% correct or is there a point where the userspace updates stop and
> only then it is needed to be stable?

It needs to be 100% correct all the time. The reason is that, as 
mentioned above, every job can carry in- and out-fences, such that 
userspace can order these jobs against the execution of shaders.

This is also why there could be jobs queued up, where all of them apply 
changes to the same region within the VA space, since there might be 
shader executions (or just memory copies) ordered right between them.

- Danilo

> 
>>
>> So, the only way to go seems to be to use mas_store_gfp() with GFP_ATOMIC
>> directly in the fence signalling critical path. I guess mas_store_gfp() does
>> not BUG_ON() if it can't get atomic pages?
>>
>> Also, I just saw that the tree is limited in it's height (MAPLE_HEIGHT_MAX).
>> Do you think it could be a sane alternative to pre-allocate with
>> MAPLE_HEIGHT_MAX rather than to rely on atomic pages? Or maybe a compromise
>> of pre-allocating just a couple of nodes and then rely on atomic pages for
>> the rest?
>>
>> FYI, we're talking about a magnitude of hundreds of thousands of entries to
>> be stored in the tree.
>>
> 
> Since you are not tracking gaps, you will get 16 entries per node.  The
> maximum height is 31, so that would be 16^31, assuming a gap between
> each entry (the worst case), you can cut that in 1/2.  To assure you can
> successfully allocate storage for a new entries, you'd need to allocate
> 30 * 3 + 1, or 91 nodes, which is 6 pages.  That'll be highly wasteful
> as almost all of these would be freed, and sometimes all of them.
> 
> You estimate less than 1M entries, that would never go over 6 levels (8.3M
> entries with the worst-case).  5 levels would get you 500K in the worst
> case, but realistically you'll be in the 5 levels almost always.  So,
> 5*3+1 = 17 nodes, or 2 pages (1 node over 1 page).. assuming 4k pages.
> 
> [1] https://lore.kernel.org/linux-mm/20230620004217.4700-8-dakr@redhat.com/T/#Z2e.:..:20230620004217.4700-4-dakr::40redhat.com:1drivers:gpu:drm:drm_gem.c
>
  

* Danilo Krummrich <dakr@redhat.com> [230627 10:58]:
> Hi Liam,
> 
> On 6/27/23 03:58, Liam R. Howlett wrote:
> > * Danilo Krummrich <dakr@redhat.com> [230626 14:37]:
> > > On 6/26/23 16:52, Matthew Wilcox wrote:
> > > > On Mon, Jun 26, 2023 at 04:27:54PM +0200, Danilo Krummrich wrote:
> > > > > On 6/26/23 15:19, Matthew Wilcox wrote:
> > > > > > On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
> > > > > > > On the other hand, unless I miss something (and if so, please let me know),
> > > > > > > something is bogus with the API then.
> > > > > > > 
> > > > > > > While the documentation of the Advanced API of the maple tree explicitly
> > > > > > > claims that the user of the API is responsible for locking, this should be
> > > > > > > limited to the bounds set by the maple tree implementation. Which means, the
> > > > > > > user must decide for either the internal (spin-) lock or an external lock
> > > > > > > (which possibly goes away in the future) and acquire and release it
> > > > > > > according to the rules maple tree enforces through lockdep checks.
> > > > > > > 
> > > > > > > Let's say one picks the internal lock. How is one supposed to ensure the
> > > > > > > tree isn't modified using the internal lock with mas_preallocate()?
> > > > > > > 
> > > > > > > Besides that, I think the documentation should definitely mention this
> > > > > > > limitation and give some guidance for the locking.
> > > > > > > 
> > > > > > > Currently, from an API perspective, I can't see how anyone not familiar with
> > > > > > > the implementation details would be able to recognize this limitation.
> > > > > > > 
> > > > > > > In terms of the GPUVA manager, unfortunately, it seems like I need to drop
> > > > > > > the maple tree and go back to using a rb-tree, since it seems there is no
> > > > > > > sane way doing a worst-case pre-allocation that does not suffer from this
> > > > > > > limitation.
> > > > > > 
> > > > > > I haven't been paying much attention here (too many other things going
> > > > > > on), but something's wrong.
> > > > > > 
> > > > > > First, you shouldn't need to preallocate.  Preallocation is only there
> > > > > 
> > > > > Unfortunately, I think we really have a case where we have to. Typically GPU
> > > > > mappings are created in a dma-fence signalling critical path and that is
> > > > > where such mappings need to be added to the maple tree. Hence, we can't do
> > > > > any sleeping allocations there.
> > > > 
> > > > OK, so there are various ways to hadle this, depending on what's
> > > > appropriate for your case.
> > > > 
> > > > The simplest is to use GFP_ATOMIC.  Essentially, you're saying to the MM
> > > > layer "This is too hard, let me tap into the emergency reserves".  It's
> > > > mildly frowned upon, so let's see if we can do better.
> > > > 
> > > > If you know where the allocation needs to be stored, but want it to act as
> > > > NULL until the time is right, you can store a ZERO entry.  That will read
> > > > as NULL until you store to it.  A pure overwriting store will not cause
> > > > any memory allocation since all the implementation has to do is change
> > > > a pointer.  The XArray wraps this up nicely behind an xa_reserve() API.
> > > > As you're discovering, the Maple Tree API isn't fully baked yet.
> > > > 
> > > 
> > > Unfortunately, GFP_ATOMIC seems the be the only option. I think storing
> > > entries in advance would not work. Typically userspace submits a job to the
> > > kernel issuing one or multiple requests to map and unmap memory in an ioctl.
> > > Such a job is then put into a queue and processed asynchronously in a
> > > dma-fence signalling critical section. Hence, at the we'd store entries in
> > > advance we could have an arbitrary amount of pending jobs potentially still
> > > messing with the same address space region.
> > 
> > What I think you are saying is that you have a number of requests
> > flooding in, which may overwrite the same areas, but are queued up to be
> > written after they are queued.  These operations look to be kept in
> > order according to the code in nouveau_job_submit[1].  Is this correct?
> 
> That's all correct.
> 
> (Although Nouveau isn't a good example in this case. Some aspects of it do
> and some aspects of it do not apply to the problem we're discussing here.)
> 
> > 
> > So then, your issue isn't that you don't know where they will land, but
> > don't know if the area that you reserved is already split into other
> > areas?  For instance, before the range 5-10 is backed by whatever
> > happens in the fence, it may have already become 5-6 & 8-10 by something
> > that came after (from userspace) but hasn't been processed by the
> > kernel that will live at 7?  So you can't write 5-10 right away because
> > you can't be sure 5-10 is going to exist once you reach the kernel fence
> > code that stores the entry?
> > 
> > Is my understanding of your issue correct?
> 
> Yes, it is.
> 
> However, the problem already starts while trying to reserve an area. In
> order to satisfy a user request, such a request is broken down into
> operations such as unmap mappings which are in the way entirely, remap
> mappings which intersect with the requested mapping and finally map the
> requested mapping. The execution of such a sequence must appear atomic and
> hence be locked accordingly. When trying to reserve an area we'd need to
> take that lock. But since this lock would be used in the dma-fence
> signalling critical path as well we'd not be allowed to do sleeping
> allocations while holding this lock.
> 
> Potentially, this could be solved with a retry loop though. Drop the lock
> while allocating, take it again and check whether we still got enough nodes
> allocated. Analogous to what the maple tree does in mas_store_gfp(), I
> guess.
> 
> > 
> > Oh, and I guess the queued requests would have to remain ordered between
> > threads or whatever is on the other side?  I mean, you can't have two
> > threads firing different things into the kernel at the same region
> > because I would think the results would be unpredictable?
> 
> Once a job is queued up in the kernel they remain ordered.
> 
> However, user threads could concurrently push jobs to the kernel altering
> the same region of the address space - it just would not make any sense for
> userspace to do that.
> 
> In general userspace is responsible for the semantics of the address space.
> The kernel basically just takes any (valid) request and make it happen. It
> also assures waiting and signalling of fences which might be bound to
> certain jobs and obviously keeps track of the VA space to be able to clean
> things up once a client disappears.
> 
> > 
> > Can these overlapping entries partially overlap one region and another?
> > That is, can you have three in-flight writes that does something like:
> > store 1-10, store 10-20, store 5-15?
> 
> Absolutely, yes.
> 
> > 
> > How stable of an output is needed?  Does each kernel write need to be
> > 100% correct or is there a point where the userspace updates stop and
> > only then it is needed to be stable?
> 
> It needs to be 100% correct all the time. The reason is that, as mentioned
> above, every job can carry in- and out-fences, such that userspace can order
> these jobs against the execution of shaders.

But each job is split into parts, so the fences surround these groups of
operations?

Since ordering is kept, you must reach a point before entering the
fences which could call the mas_preallocate() to ensure enough nodes
exist to install the new mapping, and then no other operations will be
happening. I guess what you are saying is each fence has more than one
tree operation?

As long as you are not mapping more than a range, then this should be possible
in a single write and thus a single preallocation.  You can do this by
not actually writing unmaps/remaps to the tree within the fence.  Once
the out-fence is reached, then the operation looks atomic.

Reading your patch, it is not clear this is accurate for VM_BIND of
asynchronous syncobjs.  Is the fence spanning multiple syncobjs with
various ranges to map?  Or are these things the split-up tasks of
unmap/remap, etc that will eventually boil down to what appears to be a
single write?

> 
> This is also why there could be jobs queued up, where all of them apply
> changes to the same region within the VA space, since there might be shader
> executions (or just memory copies) ordered right between them.
> 
> - Danilo
> 
> > 
> > > 
> > > So, the only way to go seems to be to use mas_store_gfp() with GFP_ATOMIC
> > > directly in the fence signalling critical path. I guess mas_store_gfp() does
> > > not BUG_ON() if it can't get atomic pages?
> > > 
> > > Also, I just saw that the tree is limited in it's height (MAPLE_HEIGHT_MAX).
> > > Do you think it could be a sane alternative to pre-allocate with
> > > MAPLE_HEIGHT_MAX rather than to rely on atomic pages? Or maybe a compromise
> > > of pre-allocating just a couple of nodes and then rely on atomic pages for
> > > the rest?
> > > 
> > > FYI, we're talking about a magnitude of hundreds of thousands of entries to
> > > be stored in the tree.
> > > 
> > 
> > Since you are not tracking gaps, you will get 16 entries per node.  The
> > maximum height is 31, so that would be 16^31, assuming a gap between
> > each entry (the worst case), you can cut that in 1/2.  To assure you can
> > successfully allocate storage for a new entries, you'd need to allocate
> > 30 * 3 + 1, or 91 nodes, which is 6 pages.  That'll be highly wasteful
> > as almost all of these would be freed, and sometimes all of them.
> > 
> > You estimate less than 1M entries, that would never go over 6 levels (8.3M
> > entries with the worst-case).  5 levels would get you 500K in the worst
> > case, but realistically you'll be in the 5 levels almost always.  So,
> > 5*3+1 = 17 nodes, or 2 pages (1 node over 1 page).. assuming 4k pages.
> > 
> > [1] https://lore.kernel.org/linux-mm/20230620004217.4700-8-dakr@redhat.com/T/#Z2e.:..:20230620004217.4700-4-dakr::40redhat.com:1drivers:gpu:drm:drm_gem.c
> > 
>
  

On 6/27/23 18:11, Liam R. Howlett wrote:
> * Danilo Krummrich <dakr@redhat.com> [230627 10:58]:
>> Hi Liam,
>>
>> On 6/27/23 03:58, Liam R. Howlett wrote:
>>> * Danilo Krummrich <dakr@redhat.com> [230626 14:37]:
>>>> On 6/26/23 16:52, Matthew Wilcox wrote:
>>>>> On Mon, Jun 26, 2023 at 04:27:54PM +0200, Danilo Krummrich wrote:
>>>>>> On 6/26/23 15:19, Matthew Wilcox wrote:
>>>>>>> On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
>>>>>>>> On the other hand, unless I miss something (and if so, please let me know),
>>>>>>>> something is bogus with the API then.
>>>>>>>>
>>>>>>>> While the documentation of the Advanced API of the maple tree explicitly
>>>>>>>> claims that the user of the API is responsible for locking, this should be
>>>>>>>> limited to the bounds set by the maple tree implementation. Which means, the
>>>>>>>> user must decide for either the internal (spin-) lock or an external lock
>>>>>>>> (which possibly goes away in the future) and acquire and release it
>>>>>>>> according to the rules maple tree enforces through lockdep checks.
>>>>>>>>
>>>>>>>> Let's say one picks the internal lock. How is one supposed to ensure the
>>>>>>>> tree isn't modified using the internal lock with mas_preallocate()?
>>>>>>>>
>>>>>>>> Besides that, I think the documentation should definitely mention this
>>>>>>>> limitation and give some guidance for the locking.
>>>>>>>>
>>>>>>>> Currently, from an API perspective, I can't see how anyone not familiar with
>>>>>>>> the implementation details would be able to recognize this limitation.
>>>>>>>>
>>>>>>>> In terms of the GPUVA manager, unfortunately, it seems like I need to drop
>>>>>>>> the maple tree and go back to using a rb-tree, since it seems there is no
>>>>>>>> sane way doing a worst-case pre-allocation that does not suffer from this
>>>>>>>> limitation.
>>>>>>>
>>>>>>> I haven't been paying much attention here (too many other things going
>>>>>>> on), but something's wrong.
>>>>>>>
>>>>>>> First, you shouldn't need to preallocate.  Preallocation is only there
>>>>>>
>>>>>> Unfortunately, I think we really have a case where we have to. Typically GPU
>>>>>> mappings are created in a dma-fence signalling critical path and that is
>>>>>> where such mappings need to be added to the maple tree. Hence, we can't do
>>>>>> any sleeping allocations there.
>>>>>
>>>>> OK, so there are various ways to hadle this, depending on what's
>>>>> appropriate for your case.
>>>>>
>>>>> The simplest is to use GFP_ATOMIC.  Essentially, you're saying to the MM
>>>>> layer "This is too hard, let me tap into the emergency reserves".  It's
>>>>> mildly frowned upon, so let's see if we can do better.
>>>>>
>>>>> If you know where the allocation needs to be stored, but want it to act as
>>>>> NULL until the time is right, you can store a ZERO entry.  That will read
>>>>> as NULL until you store to it.  A pure overwriting store will not cause
>>>>> any memory allocation since all the implementation has to do is change
>>>>> a pointer.  The XArray wraps this up nicely behind an xa_reserve() API.
>>>>> As you're discovering, the Maple Tree API isn't fully baked yet.
>>>>>
>>>>
>>>> Unfortunately, GFP_ATOMIC seems the be the only option. I think storing
>>>> entries in advance would not work. Typically userspace submits a job to the
>>>> kernel issuing one or multiple requests to map and unmap memory in an ioctl.
>>>> Such a job is then put into a queue and processed asynchronously in a
>>>> dma-fence signalling critical section. Hence, at the we'd store entries in
>>>> advance we could have an arbitrary amount of pending jobs potentially still
>>>> messing with the same address space region.
>>>
>>> What I think you are saying is that you have a number of requests
>>> flooding in, which may overwrite the same areas, but are queued up to be
>>> written after they are queued.  These operations look to be kept in
>>> order according to the code in nouveau_job_submit[1].  Is this correct?
>>
>> That's all correct.
>>
>> (Although Nouveau isn't a good example in this case. Some aspects of it do
>> and some aspects of it do not apply to the problem we're discussing here.)
>>
>>>
>>> So then, your issue isn't that you don't know where they will land, but
>>> don't know if the area that you reserved is already split into other
>>> areas?  For instance, before the range 5-10 is backed by whatever
>>> happens in the fence, it may have already become 5-6 & 8-10 by something
>>> that came after (from userspace) but hasn't been processed by the
>>> kernel that will live at 7?  So you can't write 5-10 right away because
>>> you can't be sure 5-10 is going to exist once you reach the kernel fence
>>> code that stores the entry?
>>>
>>> Is my understanding of your issue correct?
>>
>> Yes, it is.
>>
>> However, the problem already starts while trying to reserve an area. In
>> order to satisfy a user request, such a request is broken down into
>> operations such as unmap mappings which are in the way entirely, remap
>> mappings which intersect with the requested mapping and finally map the
>> requested mapping. The execution of such a sequence must appear atomic and
>> hence be locked accordingly. When trying to reserve an area we'd need to
>> take that lock. But since this lock would be used in the dma-fence
>> signalling critical path as well we'd not be allowed to do sleeping
>> allocations while holding this lock.
>>
>> Potentially, this could be solved with a retry loop though. Drop the lock
>> while allocating, take it again and check whether we still got enough nodes
>> allocated. Analogous to what the maple tree does in mas_store_gfp(), I
>> guess.
>>
>>>
>>> Oh, and I guess the queued requests would have to remain ordered between
>>> threads or whatever is on the other side?  I mean, you can't have two
>>> threads firing different things into the kernel at the same region
>>> because I would think the results would be unpredictable?
>>
>> Once a job is queued up in the kernel they remain ordered.
>>
>> However, user threads could concurrently push jobs to the kernel altering
>> the same region of the address space - it just would not make any sense for
>> userspace to do that.
>>
>> In general userspace is responsible for the semantics of the address space.
>> The kernel basically just takes any (valid) request and make it happen. It
>> also assures waiting and signalling of fences which might be bound to
>> certain jobs and obviously keeps track of the VA space to be able to clean
>> things up once a client disappears.
>>
>>>
>>> Can these overlapping entries partially overlap one region and another?
>>> That is, can you have three in-flight writes that does something like:
>>> store 1-10, store 10-20, store 5-15?
>>
>> Absolutely, yes.
>>
>>>
>>> How stable of an output is needed?  Does each kernel write need to be
>>> 100% correct or is there a point where the userspace updates stop and
>>> only then it is needed to be stable?
>>
>> It needs to be 100% correct all the time. The reason is that, as mentioned
>> above, every job can carry in- and out-fences, such that userspace can order
>> these jobs against the execution of shaders.
> 
> But each job is split into parts, so the fences surround these groups of
> operations?

Yes, each job can have multiple requests to map or unmap something and 
each of them gets broken down into operations to make them happen. The 
fences are per job.

> 
> Since ordering is kept, you must reach a point before entering the
> fences which could call the mas_preallocate() to ensure enough nodes
> exist to install the new mapping, and then no other operations will be
> happening. I guess what you are saying is each fence has more than one
> tree operation?
> 

I guess you assume that in the asynchronous path, where jobs are fetched 
from the queue for execution, there must be a point of time before we 
enter the fence signalling critical path. This is not the case.

The fence signalling critical path is entered once the corresponding 
out-fence is published to userspace and hence becomes visible to 
userspace. This happens when the job submit ioctl() (which is where the 
job is queued up for execution) returns. Hence, all jobs in the queue 
potentially entered their fence signalling critical path already before 
they could have been fetched from the queue.

The job submit ioctl() is where we would need to call mas_preallocate(), 
but this is also where we could have concurrent modifications to the 
tree from previously submitted jobs that have been fetched from the 
queue for asynchronous execution.

> As long as you are not mapping more than a range, then this should be possible
> in a single write and thus a single preallocation.  You can do this by
> not actually writing unmaps/remaps to the tree within the fence.  Once
> the out-fence is reached, then the operation looks atomic.

As mentioned above there can be an arbitrary amount of map and unmap 
requests per job.

Also, we can have cases where we, for instance, have a mapping A[0,10] 
either already in the tree (or pending in the job queue) and a user 
requests B[4,7].

The expected result would be: A'[0,4], B[4,7] and A''[7,10]. Hence, one 
job can cause multiple writes per single map request even.

At the time the job asking to map B is submitted, A might not even be in 
the tree yet.

> 
> Reading your patch, it is not clear this is accurate for VM_BIND of
> asynchronous syncobjs.  Is the fence spanning multiple syncobjs with
> various ranges to map?  Or are these things the split-up tasks of
> unmap/remap, etc that will eventually boil down to what appears to be a
> single write?
> 

The VM_BIND ioctl() is the ioctl() mentioned above to submit (bind) 
jobs. Userspace can pass syncobjs together with a job, which can be both 
syncobj which contain fences to wait for before executing the job and 
syncobjs to install the job's fence to for userspace to wait for them or 
pass them into another kernel interface to synchronize them against 
something else.

Otherwise, as mentioned above, each job can have multiple requests to 
map or unmap something and each of them gets broken down into operations 
to make such a request happen, which themselves can be re-maps, unmaps 
and maps. For instance, an unmap request for a given range, gets broken 
down into re-maps of mappings it intersects and unmaps of mappings it 
entirely spans over.

Thanks,
Danilo

>>
>> This is also why there could be jobs queued up, where all of them apply
>> changes to the same region within the VA space, since there might be shader
>> executions (or just memory copies) ordered right between them.
>>
>> - Danilo
>>
>>>
>>>>
>>>> So, the only way to go seems to be to use mas_store_gfp() with GFP_ATOMIC
>>>> directly in the fence signalling critical path. I guess mas_store_gfp() does
>>>> not BUG_ON() if it can't get atomic pages?
>>>>
>>>> Also, I just saw that the tree is limited in it's height (MAPLE_HEIGHT_MAX).
>>>> Do you think it could be a sane alternative to pre-allocate with
>>>> MAPLE_HEIGHT_MAX rather than to rely on atomic pages? Or maybe a compromise
>>>> of pre-allocating just a couple of nodes and then rely on atomic pages for
>>>> the rest?
>>>>
>>>> FYI, we're talking about a magnitude of hundreds of thousands of entries to
>>>> be stored in the tree.
>>>>
>>>
>>> Since you are not tracking gaps, you will get 16 entries per node.  The
>>> maximum height is 31, so that would be 16^31, assuming a gap between
>>> each entry (the worst case), you can cut that in 1/2.  To assure you can
>>> successfully allocate storage for a new entries, you'd need to allocate
>>> 30 * 3 + 1, or 91 nodes, which is 6 pages.  That'll be highly wasteful
>>> as almost all of these would be freed, and sometimes all of them.
>>>
>>> You estimate less than 1M entries, that would never go over 6 levels (8.3M
>>> entries with the worst-case).  5 levels would get you 500K in the worst
>>> case, but realistically you'll be in the 5 levels almost always.  So,
>>> 5*3+1 = 17 nodes, or 2 pages (1 node over 1 page).. assuming 4k pages.
>>>
>>> [1] https://lore.kernel.org/linux-mm/20230620004217.4700-8-dakr@redhat.com/T/#Z2e.:..:20230620004217.4700-4-dakr::40redhat.com:1drivers:gpu:drm:drm_gem.c
>>>
>>
>