[PATCH] iommu/iova: Reset max32_alloc_size after cleaning rcache in the fail path

[PATCH] iommu/iova: Reset max32_alloc_size after cleaning rcache in the fail path

[yf.wang]

From: Yunfei Wang <yf.wang@mediatek.com>

In alloc_iova_fast function, if __alloc_and_insert_iova_range fail,
alloc_iova_fast will try flushing rcache and retry alloc iova, but
this has an issue:

Since __alloc_and_insert_iova_range fail will set the current alloc
iova size to max32_alloc_size (iovad->max32_alloc_size = size),
when the retry is executed into the __alloc_and_insert_iova_range
function, the retry action will be blocked by the check condition
(size >= iovad->max32_alloc_size) and goto iova32_full directly,
causes the action of retry regular alloc iova in
__alloc_and_insert_iova_range to not actually be executed.

Based on the above, so need reset max32_alloc_size before retry alloc
iova when alloc iova fail, that is set the initial dma_32bit_pfn value
of iovad to max32_alloc_size, so that the action of retry alloc iova
in __alloc_and_insert_iova_range can be executed.

Signed-off-by: Yunfei Wang <yf.wang@mediatek.com>
---
 drivers/iommu/iova.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index b28c9435b898..0c085ae8293f 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -453,6 +453,7 @@ alloc_iova_fast(struct iova_domain *iovad, unsigned long size,
 retry:
 	new_iova = alloc_iova(iovad, size, limit_pfn, true);
 	if (!new_iova) {
+		unsigned long flags;
 		unsigned int cpu;
 
 		if (!flush_rcache)
@@ -463,6 +464,12 @@ alloc_iova_fast(struct iova_domain *iovad, unsigned long size,
 		for_each_online_cpu(cpu)
 			free_cpu_cached_iovas(cpu, iovad);
 		free_global_cached_iovas(iovad);
+
+		/* Reset max32_alloc_size after flushing rcache for retry */
+		spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
+		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
+		spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+
 		goto retry;
 	}
 
-- 
2.18.0

[PATCH v2] iommu/iova: Reset max32_alloc_size after cleaning rcache in the fail path

[yf.wang]

From: Yunfei Wang <yf.wang@mediatek.com>

In alloc_iova_fast function, if __alloc_and_insert_iova_range fail,
alloc_iova_fast will try flushing rcache and retry alloc iova, but
this has an issue:

Since __alloc_and_insert_iova_range fail will set the current alloc
iova size to max32_alloc_size (iovad->max32_alloc_size = size),
when the retry is executed into the __alloc_and_insert_iova_range
function, the retry action will be blocked by the check condition
(size >= iovad->max32_alloc_size) and goto iova32_full directly,
causes the action of retry regular alloc iova in
__alloc_and_insert_iova_range to not actually be executed.

Based on the above, so need reset max32_alloc_size before retry alloc
iova when alloc iova fail, that is set the initial dma_32bit_pfn value
of iovad to max32_alloc_size, so that the action of retry alloc iova
in __alloc_and_insert_iova_range can be executed.

Signed-off-by: Yunfei Wang <yf.wang@mediatek.com>
Cc: <stable@vger.kernel.org> # 5.10.*
---
v2: Cc stable@vger.kernel.org
    1. This patch needs to be merged stable branch, add stable@vger.kernel.org
       in mail list.

---
 drivers/iommu/iova.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index b28c9435b898..0c085ae8293f 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -453,6 +453,7 @@ alloc_iova_fast(struct iova_domain *iovad, unsigned long size,
 retry:
 	new_iova = alloc_iova(iovad, size, limit_pfn, true);
 	if (!new_iova) {
+		unsigned long flags;
 		unsigned int cpu;
 
 		if (!flush_rcache)
@@ -463,6 +464,12 @@ alloc_iova_fast(struct iova_domain *iovad, unsigned long size,
 		for_each_online_cpu(cpu)
 			free_cpu_cached_iovas(cpu, iovad);
 		free_global_cached_iovas(iovad);
+
+		/* Reset max32_alloc_size after flushing rcache for retry */
+		spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
+		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
+		spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+
 		goto retry;
 	}
 
-- 
2.18.0

Re: [PATCH v2] iommu/iova: Reset max32_alloc_size after cleaning rcache in the fail path

[Robin Murphy]

On 2022-03-01 01:59, yf.wang--- via iommu wrote:
> From: Yunfei Wang <yf.wang@mediatek.com>
> 
> In alloc_iova_fast function, if __alloc_and_insert_iova_range fail,
> alloc_iova_fast will try flushing rcache and retry alloc iova, but
> this has an issue:
> 
> Since __alloc_and_insert_iova_range fail will set the current alloc
> iova size to max32_alloc_size (iovad->max32_alloc_size = size),
> when the retry is executed into the __alloc_and_insert_iova_range
> function, the retry action will be blocked by the check condition
> (size >= iovad->max32_alloc_size) and goto iova32_full directly,
> causes the action of retry regular alloc iova in
> __alloc_and_insert_iova_range to not actually be executed.
> 
> Based on the above, so need reset max32_alloc_size before retry alloc
> iova when alloc iova fail, that is set the initial dma_32bit_pfn value
> of iovad to max32_alloc_size, so that the action of retry alloc iova
> in __alloc_and_insert_iova_range can be executed.

Have you observed this making any difference in practice?

Given that both free_cpu_cached_iovas() and free_global_cached_iovas() 
call iova_magazine_free_pfns(), which calls remove_iova(), which calls 
__cached_rbnode_delete_update(), I'm thinking no...

Robin.

> Signed-off-by: Yunfei Wang <yf.wang@mediatek.com>
> Cc: <stable@vger.kernel.org> # 5.10.*
> ---
> v2: Cc stable@vger.kernel.org
>      1. This patch needs to be merged stable branch, add stable@vger.kernel.org
>         in mail list.
> 
> ---
>   drivers/iommu/iova.c | 7 +++++++
>   1 file changed, 7 insertions(+)
> 
> diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> index b28c9435b898..0c085ae8293f 100644
> --- a/drivers/iommu/iova.c
> +++ b/drivers/iommu/iova.c
> @@ -453,6 +453,7 @@ alloc_iova_fast(struct iova_domain *iovad, unsigned long size,
>   retry:
>   	new_iova = alloc_iova(iovad, size, limit_pfn, true);
>   	if (!new_iova) {
> +		unsigned long flags;
>   		unsigned int cpu;
>   
>   		if (!flush_rcache)
> @@ -463,6 +464,12 @@ alloc_iova_fast(struct iova_domain *iovad, unsigned long size,
>   		for_each_online_cpu(cpu)
>   			free_cpu_cached_iovas(cpu, iovad);
>   		free_global_cached_iovas(iovad);
> +
> +		/* Reset max32_alloc_size after flushing rcache for retry */
> +		spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
> +		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
> +		spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
> +
>   		goto retry;
>   	}
>   
> 
> 
> _______________________________________________
> iommu mailing list
> iommu@lists.linux-foundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [PATCH v2] iommu/iova: Reset max32_alloc_size after cleaning

[Miles Chen]

Hi Yunfei,

>> Since __alloc_and_insert_iova_range fail will set the current alloc
>> iova size to max32_alloc_size (iovad->max32_alloc_size = size),
>> when the retry is executed into the __alloc_and_insert_iova_range
>> function, the retry action will be blocked by the check condition
>> (size >= iovad->max32_alloc_size) and goto iova32_full directly,
>> causes the action of retry regular alloc iova in
>> __alloc_and_insert_iova_range to not actually be executed.
>> 
>> Based on the above, so need reset max32_alloc_size before retry alloc
>> iova when alloc iova fail, that is set the initial dma_32bit_pfn value
>> of iovad to max32_alloc_size, so that the action of retry alloc iova
>> in __alloc_and_insert_iova_range can be executed.
>
> Have you observed this making any difference in practice?
> 
> Given that both free_cpu_cached_iovas() and free_global_cached_iovas() 
> call iova_magazine_free_pfns(), which calls remove_iova(), which calls 
> __cached_rbnode_delete_update(), I'm thinking no...
> 
> Robin.
>

Like Robin pointed out, if some cached iovas are freed by
free_global_cached_iovas()/free_cpu_cached_iovas(), 
the max32_alloc_size should be reset to iovad->dma_32bit_pfn.

If no cached iova is freed, resetting max32_alloc_size before
the retry allocation only give us a retry. Is it possible that
other users free their iovas during the additional retry?

alloc_iova_fast()
  retry:
    alloc_iova() // failed, iovad->max32_alloc_size = size
    free_cpu_cached_iovas()
      iova_magazine_free_pfns()
        remove_iova()
	  __cached_rbnode_delete_update()
	    iovad->max32_alloc_size = iovad->dma_32bit_pfn // reset
    free_global_cached_iovas()
      iova_magazine_free_pfns()
        remove_iova()
	  __cached_rbnode_delete_update()
	    iovad->max32_alloc_size = iovad->dma_32bit_pfn // reset
    goto retry;

thanks,
Miles

Re: [PATCH v2] iommu/iova: Reset max32_alloc_size after cleaning

[Robin Murphy]

On 2022-03-01 23:29, Miles Chen via iommu wrote:
> Hi Yunfei,
> 
>>> Since __alloc_and_insert_iova_range fail will set the current alloc
>>> iova size to max32_alloc_size (iovad->max32_alloc_size = size),
>>> when the retry is executed into the __alloc_and_insert_iova_range
>>> function, the retry action will be blocked by the check condition
>>> (size >= iovad->max32_alloc_size) and goto iova32_full directly,
>>> causes the action of retry regular alloc iova in
>>> __alloc_and_insert_iova_range to not actually be executed.
>>>
>>> Based on the above, so need reset max32_alloc_size before retry alloc
>>> iova when alloc iova fail, that is set the initial dma_32bit_pfn value
>>> of iovad to max32_alloc_size, so that the action of retry alloc iova
>>> in __alloc_and_insert_iova_range can be executed.
>>
>> Have you observed this making any difference in practice?
>>
>> Given that both free_cpu_cached_iovas() and free_global_cached_iovas()
>> call iova_magazine_free_pfns(), which calls remove_iova(), which calls
>> __cached_rbnode_delete_update(), I'm thinking no...
>>
>> Robin.
>>
> 
> Like Robin pointed out, if some cached iovas are freed by
> free_global_cached_iovas()/free_cpu_cached_iovas(),
> the max32_alloc_size should be reset to iovad->dma_32bit_pfn.
> 
> If no cached iova is freed, resetting max32_alloc_size before
> the retry allocation only give us a retry. Is it possible that
> other users free their iovas during the additional retry?

No, it's not possible, since everyone's serialised by iova_rbtree_lock. 
If the caches were already empty and the retry gets the lock first, it 
will still fail again - forcing a reset of max32_alloc_size only means 
it has to take the slow path to that failure. If another caller *did* 
manage to get in and free something between free_global_cached_iovas() 
dropping the lock and alloc_iova() re-taking it, then that would have 
legitimately reset max32_alloc_size anyway.

Thanks,
Robin.

> alloc_iova_fast()
>    retry:
>      alloc_iova() // failed, iovad->max32_alloc_size = size
>      free_cpu_cached_iovas()
>        iova_magazine_free_pfns()
>          remove_iova()
> 	  __cached_rbnode_delete_update()
> 	    iovad->max32_alloc_size = iovad->dma_32bit_pfn // reset
>      free_global_cached_iovas()
>        iova_magazine_free_pfns()
>          remove_iova()
> 	  __cached_rbnode_delete_update()
> 	    iovad->max32_alloc_size = iovad->dma_32bit_pfn // reset
>      goto retry;
> 
> thanks,
> Miles
> _______________________________________________
> iommu mailing list
> iommu@lists.linux-foundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [PATCH v2] iommu/iova: Reset max32_alloc_size after cleaning

[Miles Chen]

>> If no cached iova is freed, resetting max32_alloc_size before
>> the retry allocation only give us a retry. Is it possible that
>> other users free their iovas during the additional retry?
>
> No, it's not possible, since everyone's serialised by iova_rbtree_lock. 
> If the caches were already empty and the retry gets the lock first, it 
> will still fail again - forcing a reset of max32_alloc_size only means 
> it has to take the slow path to that failure. If another caller *did* 
> manage to get in and free something between free_global_cached_iovas() 
> dropping the lock and alloc_iova() re-taking it, then that would have 
> legitimately reset max32_alloc_size anyway.

Thanks for your explanation.

YF showed me some numbers yesterday and maybe we can have a further
discussion in that test case. (It looks like that some iovas are freed but
their pfn_lo(s) are less than cached_iova->pfn_lo, so max32_alloc_size is not
reset. So there are enought free iovas but the allocation still failed)

__cached_rbnode_delete_update(struct iova_domain *iovad, struct iova *free)
{
	struct iova *cached_iova;

	cached_iova = to_iova(iovad->cached32_node);
	if (free == cached_iova ||
		(free->pfn_hi < iovad->dma_32bit_pfn &&
		 free->pfn_lo >= cached_iova->pfn_lo)) {
		iovad->cached32_node = rb_next(&free->node);
		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
	}
	...
}

Hi YF,
Could your share your observation of the iova allocation failure you hit?

Thanks,
Miles

Re: [PATCH v2] iommu/iova: Reset max32_alloc_size after cleaning

[yf.wang]

From: yf.wang@mediatek.com <yf.wang@medaitek.com>

On Thu, 2022-03-03 at 07:52 +0800, Miles Chen wrote:
> Thanks for your explanation.
> 
> YF showed me some numbers yesterday and maybe we can have a further
> discussion in that test case. (It looks like that some iovas are
> freed but
> their pfn_lo(s) are less than cached_iova->pfn_lo, so
> max32_alloc_size is not
> reset. So there are enought free iovas but the allocation still
> failed)
> 
> __cached_rbnode_delete_update(struct iova_domain *iovad, struct iova
> *free)
> {
>       struct iova *cached_iova;
> 
>       cached_iova = to_iova(iovad->cached32_node);
>       if (free == cached_iova ||
>               (free->pfn_hi < iovad->dma_32bit_pfn &&
>                free->pfn_lo >= cached_iova->pfn_lo)) {
>               iovad->cached32_node = rb_next(&free->node);
>               iovad->max32_alloc_size = iovad->dma_32bit_pfn;
>       }
>       ...
> }
> 
> Hi YF,
> Could your share your observation of the iova allocation failure you
> hit?
> 
> Thanks,
> Miles

Hi Miles & Robin,

The scenario we encountered in our actual test:
An iova domain with a 3GB iova region (0x4000_0000~0x1_0000_0000),
only alloc iova total size 614788KB), then alloc iova size=0x731f000
fail, and then the retry mechanism is free 300 cache iova at first,
and then retry still fail, the reason for fail is blocked by the
check condition (size >= iovad->max32_alloc_size) and goto iova32_full
directly.

Why is no reset max32_alloc_size in __cached_rbnode_delete_update?
Because of the pfn_lo of the freed cache iova is smaller than the
current cached32_node's pfn_lo (free->pfn_lo < cached_iova->pfn_lo),
so will not execute (iovad->max32_alloc_size = iovad->dma_32bit_pfn),
is blocked by the check condition (free->pfn_lo >= cached_iova-
>pfn_lo).

The issue observed during stress testing, when alloc fail reset
max32_alloc_size to retry can help to allocate iova to those lower
addresses.


The following is the actual stress test log dump: 
('pfn_lo', 'size' and 'pfn_hi' has iova_shift in dump log)
size:                 0x731f000
max32_alloc_size:     0x731f000
cached_iova:          0xffffff814751a1c0
cached_iova->pfn_lo:  0xf3500000
cached_iova->pfn_hi:  0xf35ff000

1.__alloc_and_insert_iova_range_fail
[name:iova&]__alloc_and_insert_iova_range_fail:
iovad:0xffffff80d5be2808
  {granule:0x1000, start_pfn:0x40000, dma_32bit_pfn:0x100000,
  max32_alloc_size:0x731f},size:0x731f

2.dump all iova nodes of rbtree, contain cached iova:
[name:iova&]dump_iova_rbtree start, iovad:0xffffff80d5be2808
  {rbroot:0xffffff814751a4c0, cached_node:0xffffff80d5be2860,
  cached32_node:0xffffff814751a1c0, granule:0x1000, start_pfn:0x40000,
  dma_32bit_pfn:0x100000, max32_alloc_size:0x731f}

('pfn_lo', 'size' and 'pfn_hi' has iova_shift in dump log)
[name:iova&]index    iova_object       pfn_lo     size       pfn_hi
[name:iova&]  1 0xffffff814751ae00  0x40800000  0x4c9000     0x40cc8000
[name:iova&]  2 0xffffff807c960880  0x40d00000  0xc4000      0x40dc3000
  ...322 lines of log are omitted here...
[name:iova&]325 0xffffff814751a1c0  0xf3500000  0x100000     0xf35ff000
[name:iova&]326 0xffffff8004552080  0xf3600000  0x100000     0xf36ff000
[name:iova&]327 0xffffff80045524c0  0xf3700000  0xbc000      0xf37bb000
[name:iova&]328 0xffffff814751a700  0xf3800000  0x265000     0xf3a64000
[name:iova&]329 0xffffff8004552180  0xf3c00000  0xa13000     0xf4612000
[name:iova&]330 0xffffff80c1b3eb40  0xf4800000  0xb400000    0xffbff000
[name:iova&]331 0xffffff80d6e0b580  0xffcff000  0x1000       0xffcff000
[name:iova&]332 0xffffff80c8395140  0xffd00000  0x80000      0xffd7f000
[name:iova&]333 0xffffff80c8395000  0xffde0000  0x20000      0xffdff000
[name:iova&]334 0xffffff80c8395380  0xffe00000  0x80000      0xffe7f000
[name:iova&]335 0xffffff80c8395880  0xffec0000  0x20000      0xffedf000
[name:iova&]336 0xffffff80c83957c0  0xffef9000  0x1000       0xffef9000
[name:iova&]337 0xffffff80c83956c0  0xffefa000  0x1000       0xffefa000
[name:iova&]338 0xffffff80c8395f40  0xffefb000  0x1000       0xffefb000
[name:iova&]339 0xffffff80c8395a80  0xffefc000  0x4000       0xffeff000
[name:iova&]340 0xffffff80c1b3e840  0xfff00000  0x100000     0xfffff000
[name:iova&]341 0xffffff80d5be2860  0xfffffffffffff000 0x1000
0xfffffffffffff000
[name:iova&]dump_iova_rbtree done, iovad:0xffffff80d5be2808,
  count:341, total_size:625876KB

3.alloc fail, flushing rcache and retry.
[name:iova&]alloc_iova_fast, flushing rcache and retry,
  iovad:0xffffff80d5be2808, size:0x731f, limit_pfn:0xfffff

4.retry is executed into the __alloc_and_insert_iova_range function:
[name:iova&]__alloc_and_insert_iova_range fail goto iova32_full,
  iovad:0xffffff80d5be2808 {granule:0x1000, start_pfn:0x40000,
  dma_32bit_pfn:0x100000, max32_alloc_size:0x731f},size:0x731f

5.dump all iova nodes of rbtree, current caches is already empty:
[name:iova&]dump_iova_rbtree start, iovad:0xffffff80d5be2808
  {rbroot:0xffffff80fe76da80, cached_node:0xffffff80d5be2860,
  cached32_node:0xffffff814751a1c0, granule:0x1000, start_pfn:0x40000,
  dma_32bit_pfn:0x100000, max32_alloc_size:0x731f}

('pfn_lo', 'size' and 'pfn_hi' has iova_shift in dump log)
[name:iova&]index    iova_object       pfn_lo     size       pfn_hi
[name:iova&]  1 0xffffff814751ae00  0x40800000  0x4c9000     0x40cc8000
[name:iova&]  2 0xffffff807c960880  0x40d00000  0xc4000      0x40dc3000
[name:iova&]  3 0xffffff81487ce840  0x40e00000  0x37a000     0x41179000
[name:iova&]  4 0xffffff80fe76d600  0x41200000  0x2400000    0x435ff000
[name:iova&]  5 0xffffff8004552000  0x46800000  0x47e2000    0x4afe1000
[name:iova&]  6 0xffffff807c960a40  0x50200000  0x400000     0x505ff000
[name:iova&]  7 0xffffff818cdb5780  0x50600000  0x265000     0x50864000
[name:iova&]  8 0xffffff814751a440  0x50a00000  0x2ae000     0x50cad000
[name:iova&]  9 0xffffff818cdb5d40  0x50e00000  0x4c9000     0x512c8000
[name:iova&] 10 0xffffff81487cef40  0x51400000  0x1a25000    0x52e24000
[name:iova&] 11 0xffffff818cdb5140  0x53c00000  0x400000     0x53fff000
[name:iova&] 12 0xffffff814751a7c0  0x54000000  0x400000     0x543ff000
[name:iova&] 13 0xffffff80fe76d2c0  0x54500000  0xbc000      0x545bb000
[name:iova&] 14 0xffffff81487ce0c0  0x54600000  0x400000     0x549ff000
[name:iova&] 15 0xffffff80fe76d740  0x54a00000  0xbc000      0x54abb000
[name:iova&] 16 0xffffff8004552440  0x54b00000  0xbc000      0x54bbb000
[name:iova&] 17 0xffffff80fe76db80  0x54c00000  0x47e2000    0x593e1000
[name:iova&] 18 0xffffff818cdb5440  0x65000000  0x400000     0x653ff000
[name:iova&] 19 0xffffff8004552880  0x65400000  0x47e2000    0x69be1000
[name:iova&] 20 0xffffff814751acc0  0x6c7e0000  0x20000      0x6c7ff000
[name:iova&] 21 0xffffff80fe76d700  0x6c800000  0x47e2000    0x70fe1000
//0x70fe1000 - 0xebc00000 = 0x7ac1f000:This free range is large enough
[name:iova&] 22 0xffffff80fe76da80  0xebc00000  0x400000     0xebfff000
[name:iova&] 23 0xffffff80045523c0  0xec000000  0x400000     0xec3ff000
[name:iova&] 24 0xffffff8004552780  0xec400000  0x400000     0xec7ff000
[name:iova&] 25 0xffffff814751a1c0  0xf3500000  0x100000     0xf35ff000
[name:iova&] 26 0xffffff8004552080  0xf3600000  0x100000     0xf36ff000
[name:iova&] 27 0xffffff80045524c0  0xf3700000  0xbc000      0xf37bb000
[name:iova&] 28 0xffffff814751a700  0xf3800000  0x265000     0xf3a64000
[name:iova&] 29 0xffffff8004552180  0xf3c00000  0xa13000     0xf4612000
[name:iova&] 30 0xffffff80c1b3eb40  0xf4800000  0xb400000    0xffbff000
[name:iova&] 31 0xffffff80d6e0b580  0xffcff000  0x1000       0xffcff000
[name:iova&] 32 0xffffff80c8395140  0xffd00000  0x80000      0xffd7f000
[name:iova&] 33 0xffffff80c8395000  0xffde0000  0x20000      0xffdff000
[name:iova&] 34 0xffffff80c8395380  0xffe00000  0x80000      0xffe7f000
[name:iova&] 35 0xffffff80c8395880  0xffec0000  0x20000      0xffedf000
[name:iova&] 36 0xffffff80c83957c0  0xffef9000  0x1000       0xffef9000
[name:iova&] 37 0xffffff80c83956c0  0xffefa000  0x1000       0xffefa000
[name:iova&] 38 0xffffff80c8395f40  0xffefb000  0x1000       0xffefb000
[name:iova&] 39 0xffffff80c8395a80  0xffefc000  0x4000       0xffeff000
[name:iova&] 40 0xffffff80c1b3e840  0xfff00000  0x100000     0xfffff000
[name:iova&] 41 0xffffff80d5be2860  0xfffffffffffff000 0x1000
0xfffffffffffff000
[name:iova&]dump_iova_rbtree done, iovad:0xffffff80d5be2808,
count:41, total_size:614788KB

Thanks,
Yunfei.

Re: [PATCH v2] iommu/iova: Reset max32_alloc_size after cleaning

[Robin Murphy]

On 2022-03-03 03:43, yf.wang@mediatek.com wrote:
> On Thu, 2022-03-03 at 07:52 +0800, Miles Chen wrote:
>> Thanks for your explanation.
>>
>> YF showed me some numbers yesterday and maybe we can have a further
>> discussion in that test case. (It looks like that some iovas are
>> freed but
>> their pfn_lo(s) are less than cached_iova->pfn_lo, so
>> max32_alloc_size is not
>> reset. So there are enought free iovas but the allocation still
>> failed)
>>
>> __cached_rbnode_delete_update(struct iova_domain *iovad, struct iova
>> *free)
>> {
>> 	struct iova *cached_iova;
>>
>> 	cached_iova = to_iova(iovad->cached32_node);
>> 	if (free == cached_iova ||
>> 		(free->pfn_hi < iovad->dma_32bit_pfn &&
>> 		 free->pfn_lo >= cached_iova->pfn_lo)) {
>> 		iovad->cached32_node = rb_next(&free->node);
>> 		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
>> 	}
>> 	...
>> }
>>
>> Hi YF,
>> Could your share your observation of the iova allocation failure you
>> hit?
>>
>> Thanks,
>> Miles
> 
> Hi Miles & Robin,
> 
> The scenario we encountered in our actual test:
> An iova domain with a 3GB iova region (0x4000_0000~0x1_0000_0000),
> only alloc iova total size 614788KB), then alloc iova size=0x731f000
> fail, and then the retry mechanism is free 300 cache iova at first,
> and then retry still fail, the reason for fail is blocked by the
> check condition (size >= iovad->max32_alloc_size) and goto iova32_full
> directly.
> 
> Why is no reset max32_alloc_size in __cached_rbnode_delete_update?
> Because of the pfn_lo of the freed cache iova is smaller than the
> current cached32_node's pfn_lo (free->pfn_lo < cached_iova->pfn_lo),
> so will not execute (iovad->max32_alloc_size = iovad->dma_32bit_pfn),
> is blocked by the check condition (free->pfn_lo >= cached_iova-
>> pfn_lo).
> 
> The issue observed during stress testing, when alloc fail reset
> max32_alloc_size to retry can help to allocate iova to those lower
> addresses.

Oh, now I see what's going on, thanks for clarifying. This is a 
wonderfully obscure corner case, but ultimately what comes out of it is 
that there's an assumption in __cached_rbnode_delete_update() which I 
think was OK at the time it was written (due to other limitations), but 
now deserves to be remedied.

The proper fix is simple to make, but I think I'll need to have my lunch 
before trying to write up the reasoning behind it for a patch... :)

Thanks,
Robin.

> The following is the actual stress test log dump:
> ('pfn_lo', 'size' and 'pfn_hi' has iova_shift in dump log)
> size:                 0x731f000
> max32_alloc_size:     0x731f000
> cached_iova:          0xffffff814751a1c0
> cached_iova->pfn_lo:  0xf3500000
> cached_iova->pfn_hi:  0xf35ff000
> 
> 1.__alloc_and_insert_iova_range_fail
> [name:iova&]__alloc_and_insert_iova_range_fail:
> iovad:0xffffff80d5be2808
>    {granule:0x1000, start_pfn:0x40000, dma_32bit_pfn:0x100000,
>    max32_alloc_size:0x731f},size:0x731f
> 
> 2.dump all iova nodes of rbtree, contain cached iova:
> [name:iova&]dump_iova_rbtree start, iovad:0xffffff80d5be2808
>    {rbroot:0xffffff814751a4c0, cached_node:0xffffff80d5be2860,
>    cached32_node:0xffffff814751a1c0, granule:0x1000, start_pfn:0x40000,
>    dma_32bit_pfn:0x100000, max32_alloc_size:0x731f}
> 
> ('pfn_lo', 'size' and 'pfn_hi' has iova_shift in dump log)
> [name:iova&]index    iova_object       pfn_lo     size       pfn_hi
> [name:iova&]  1 0xffffff814751ae00  0x40800000  0x4c9000     0x40cc8000
> [name:iova&]  2 0xffffff807c960880  0x40d00000  0xc4000      0x40dc3000
>    ...322 lines of log are omitted here...
> [name:iova&]325 0xffffff814751a1c0  0xf3500000  0x100000     0xf35ff000
> [name:iova&]326 0xffffff8004552080  0xf3600000  0x100000     0xf36ff000
> [name:iova&]327 0xffffff80045524c0  0xf3700000  0xbc000      0xf37bb000
> [name:iova&]328 0xffffff814751a700  0xf3800000  0x265000     0xf3a64000
> [name:iova&]329 0xffffff8004552180  0xf3c00000  0xa13000     0xf4612000
> [name:iova&]330 0xffffff80c1b3eb40  0xf4800000  0xb400000    0xffbff000
> [name:iova&]331 0xffffff80d6e0b580  0xffcff000  0x1000       0xffcff000
> [name:iova&]332 0xffffff80c8395140  0xffd00000  0x80000      0xffd7f000
> [name:iova&]333 0xffffff80c8395000  0xffde0000  0x20000      0xffdff000
> [name:iova&]334 0xffffff80c8395380  0xffe00000  0x80000      0xffe7f000
> [name:iova&]335 0xffffff80c8395880  0xffec0000  0x20000      0xffedf000
> [name:iova&]336 0xffffff80c83957c0  0xffef9000  0x1000       0xffef9000
> [name:iova&]337 0xffffff80c83956c0  0xffefa000  0x1000       0xffefa000
> [name:iova&]338 0xffffff80c8395f40  0xffefb000  0x1000       0xffefb000
> [name:iova&]339 0xffffff80c8395a80  0xffefc000  0x4000       0xffeff000
> [name:iova&]340 0xffffff80c1b3e840  0xfff00000  0x100000     0xfffff000
> [name:iova&] 41 0xffffff80d5be2860  0xfffffffffffff000 0x1000
> 0xfffffffffffff000
> [name:iova&]dump_iova_rbtree done, iovad:0xffffff80d5be2808,
>    count:341, total_size:625876KB
> 
> 3.alloc fail, flushing rcache and retry.
> [name:iova&]alloc_iova_fast, flushing rcache and retry,
>    iovad:0xffffff80d5be2808, size:0x731f, limit_pfn:0xfffff
> 
> 4.retry is executed into the __alloc_and_insert_iova_range function:
> [name:iova&]__alloc_and_insert_iova_range fail goto iova32_full,
>    iovad:0xffffff80d5be2808 {granule:0x1000, start_pfn:0x40000,
>    dma_32bit_pfn:0x100000, max32_alloc_size:0x731f},size:0x731f
> 
> 5.dump all iova nodes of rbtree, current caches is already empty:
> [name:iova&]dump_iova_rbtree start, iovad:0xffffff80d5be2808
>    {rbroot:0xffffff80fe76da80, cached_node:0xffffff80d5be2860,
>    cached32_node:0xffffff814751a1c0, granule:0x1000, start_pfn:0x40000,
>    dma_32bit_pfn:0x100000, max32_alloc_size:0x731f}
> 
> ('pfn_lo', 'size' and 'pfn_hi' has iova_shift in dump log)
> [name:iova&]index    iova_object       pfn_lo     size       pfn_hi
> [name:iova&]  1 0xffffff814751ae00  0x40800000  0x4c9000     0x40cc8000
> [name:iova&]  2 0xffffff807c960880  0x40d00000  0xc4000      0x40dc3000
> [name:iova&]  3 0xffffff81487ce840  0x40e00000  0x37a000     0x41179000
> [name:iova&]  4 0xffffff80fe76d600  0x41200000  0x2400000    0x435ff000
> [name:iova&]  5 0xffffff8004552000  0x46800000  0x47e2000    0x4afe1000
> [name:iova&]  6 0xffffff807c960a40  0x50200000  0x400000     0x505ff000
> [name:iova&]  7 0xffffff818cdb5780  0x50600000  0x265000     0x50864000
> [name:iova&]  8 0xffffff814751a440  0x50a00000  0x2ae000     0x50cad000
> [name:iova&]  9 0xffffff818cdb5d40  0x50e00000  0x4c9000     0x512c8000
> [name:iova&] 10 0xffffff81487cef40  0x51400000  0x1a25000    0x52e24000
> [name:iova&] 11 0xffffff818cdb5140  0x53c00000  0x400000     0x53fff000
> [name:iova&] 12 0xffffff814751a7c0  0x54000000  0x400000     0x543ff000
> [name:iova&] 13 0xffffff80fe76d2c0  0x54500000  0xbc000      0x545bb000
> [name:iova&] 14 0xffffff81487ce0c0  0x54600000  0x400000     0x549ff000
> [name:iova&] 15 0xffffff80fe76d740  0x54a00000  0xbc000      0x54abb000
> [name:iova&] 16 0xffffff8004552440  0x54b00000  0xbc000      0x54bbb000
> [name:iova&] 17 0xffffff80fe76db80  0x54c00000  0x47e2000    0x593e1000
> [name:iova&] 18 0xffffff818cdb5440  0x65000000  0x400000     0x653ff000
> [name:iova&] 19 0xffffff8004552880  0x65400000  0x47e2000    0x69be1000
> [name:iova&] 20 0xffffff814751acc0  0x6c7e0000  0x20000      0x6c7ff000
> [name:iova&] 21 0xffffff80fe76d700  0x6c800000  0x47e2000    0x70fe1000
> //0x70fe1000 - 0xebc00000 = 0x7ac1f000:This free range is large enough
> [name:iova&] 22 0xffffff80fe76da80  0xebc00000  0x400000     0xebfff000
> [name:iova&] 23 0xffffff80045523c0  0xec000000  0x400000     0xec3ff000
> [name:iova&] 24 0xffffff8004552780  0xec400000  0x400000     0xec7ff000
> [name:iova&] 25 0xffffff814751a1c0  0xf3500000  0x100000     0xf35ff000
> [name:iova&] 26 0xffffff8004552080  0xf3600000  0x100000     0xf36ff000
> [name:iova&] 27 0xffffff80045524c0  0xf3700000  0xbc000      0xf37bb000
> [name:iova&] 28 0xffffff814751a700  0xf3800000  0x265000     0xf3a64000
> [name:iova&] 29 0xffffff8004552180  0xf3c00000  0xa13000     0xf4612000
> [name:iova&] 30 0xffffff80c1b3eb40  0xf4800000  0xb400000    0xffbff000
> [name:iova&] 31 0xffffff80d6e0b580  0xffcff000  0x1000       0xffcff000
> [name:iova&] 32 0xffffff80c8395140  0xffd00000  0x80000      0xffd7f000
> [name:iova&] 33 0xffffff80c8395000  0xffde0000  0x20000      0xffdff000
> [name:iova&] 34 0xffffff80c8395380  0xffe00000  0x80000      0xffe7f000
> [name:iova&] 35 0xffffff80c8395880  0xffec0000  0x20000      0xffedf000
> [name:iova&] 36 0xffffff80c83957c0  0xffef9000  0x1000       0xffef9000
> [name:iova&] 37 0xffffff80c83956c0  0xffefa000  0x1000       0xffefa000
> [name:iova&] 38 0xffffff80c8395f40  0xffefb000  0x1000       0xffefb000
> [name:iova&] 39 0xffffff80c8395a80  0xffefc000  0x4000       0xffeff000
> [name:iova&] 40 0xffffff80c1b3e840  0xfff00000  0x100000     0xfffff000
> [name:iova&] 41 0xffffff80d5be2860  0xfffffffffffff000 0x1000
> 0xfffffffffffff000
> [name:iova&]dump_iova_rbtree done, iovad:0xffffff80d5be2808,
> count:41, total_size:614788KB
> 
> Thanks,
> Yunfei.
>