Fix Fix fence merge handling
Subsystems (3)
Hi guys,
turned out that userspace can also merge dma_fence_chain contains which can result in really huge arrays.
Fix those merges to sort the arrays and remove the duplicates. Additional to that start to use kvzalloc() for dma_fence_array containers so that can handle much larger arrays if necessary.
Please review and comment,
Christian.
PATCH 1/3 dma-buf/dma-fence_array: use kvzalloc
Reports indicates that some userspace applications try to merge more than 80k of fences into a single dma_fence_array leading to a warning from kzalloc() that the requested size becomes to big.
While that is clearly an userspace bug we should probably handle that case gracefully in the kernel.
So we can either reject requests to merge more than a reasonable amount of fences (64k maybe?) or we can start to use kvzalloc() instead of kzalloc(). This patch here does the later.
--- drivers/dma-buf/dma-fence-array.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
drivers/dma-buf/dma-fence-array.c +3 -3
@@ -119,8 +119,8 @@ static void dma_fence_array_release(struct dma_fence *fence)for (i =0 ; i < array->num_fences; ++i)dma_fence_put (array->fences[i]); -kfree (array->fences); -dma_fence_free (fence); +kvfree (array->fences); +kvfree_rcu (fence, rcu); } static void dma_fence_array_set_deadline(struct dma_fence *fence,
@@ -153,7 +153,7 @@ struct dma_fence_array *dma_fence_array_alloc(int num_fences) {struct dma_fence_array *array; -return kzalloc (struct_size (array, callbacks, num_fences),GFP_KERNEL ); +return kvzalloc (struct_size (array, callbacks, num_fences),GFP_KERNEL ); }EXPORT_SYMBOL (dma_fence_array_alloc);
Signature · 1 line
2.34.1
Re: [PATCH 1/3] dma-buf/dma-fence_array: use kvzalloc
Quoted 2 lines · Christian König
Reports indicates that some userspace applications try to merge more than 80k of fences into a single
dma_fence_arrayleading to a warning from
Really, yikes.
Quoted 9 lines
kzalloc()that the requested size becomes to big.While that is clearly an userspace bug we should probably handle that case gracefully in the kernel.
So we can either reject requests to merge more than a reasonable amount of fences (64k maybe?) or we can start to use
kvzalloc()instead ofkzalloc(). This patch here does the later.
This patch seems reasonable to me if the above use is in fact valid.
Quoted 2 lines
Signed-off-by Christian König <[email protected]>
Fixes tag?
Patch itself LGTM:
Quoted 31 lines
--- drivers/dma-buf/dma-fence-array.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)drivers/dma-buf/dma-fence-array.c +3
-3@@ -119,8 +119,8 @@ static void dma_fence_array_release(struct dma_fence *fence)for (i =0 ; i < array->num_fences; ++i)dma_fence_put (array->fences[i]); -kfree (array->fences); -dma_fence_free (fence); +kvfree (array->fences); +kvfree_rcu (fence, rcu); } static void dma_fence_array_set_deadline(struct dma_fence *fence,@@ -153,7 +153,7 @@ struct dma_fence_array *dma_fence_array_alloc(int num_fences) {struct dma_fence_array *array; -return kzalloc (struct_size (array, callbacks, num_fences),GFP_KERNEL ); +return kvzalloc (struct_size (array, callbacks, num_fences),GFP_KERNEL ); }EXPORT_SYMBOL (dma_fence_array_alloc);Signature · 1 line
2.34.1
Re: [PATCH 1/3] dma-buf/dma-fence_array: use kvzalloc
Quoted 5 lines · Matthew Brost
Quoted 2 lines · Christian König
Reports indicates that some userspace applications try to merge more than 80k of fences into a single
dma_fence_arrayleading to a warning fromReally, yikes.
Not really IME. Unless Christian means some reports I don't have access to, the cases where userspace applications tried to do that were really just cases where the fence count exploded exponentially because dma_fence_unwrap_merge failed to actually merge identical fences (see patch 2). At no point have I actually seen apps trying to merge 80k+ unique fences.
Regards,
Friedrich
Quoted 52 lines
Quoted 10 lines
kzalloc()that the requested size becomes to big.While that is clearly an userspace bug we should probably handle that case gracefully in the kernel.
So we can either reject requests to merge more than a reasonable amount of fences (64k maybe?) or we can start to use
kvzalloc()instead ofkzalloc(). This patch here does the later.This patch seems reasonable to me if the above use is in fact valid.
Quoted 2 lines
Signed-off-by Christian König <[email protected]>Fixes tag?
Patch itself LGTM:
Reviewed-by Matthew Brost <[email protected]>Quoted 31 lines
--- drivers/dma-buf/dma-fence-array.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)drivers/dma-buf/dma-fence-array.c +3
-4@@ -119,8 +119,8 @@ static void dma_fence_array_release(struct dma_fence *fence)for (i =0 ; i < array->num_fences; ++i)dma_fence_put (array->fences[i]); -kfree (array->fences); -dma_fence_free (fence); +kvfree (array->fences); +kvfree_rcu (fence, rcu); } static void dma_fence_array_set_deadline(struct dma_fence *fence,@@ -153,7 +153,7 @@ struct dma_fence_array *dma_fence_array_alloc(int num_fences) {struct dma_fence_array *array; -return kzalloc (struct_size (array, callbacks, num_fences),GFP_KERNEL ); +return kvzalloc (struct_size (array, callbacks, num_fences),GFP_KERNEL ); }EXPORT_SYMBOL (dma_fence_array_alloc); --2.34.1
Re: [PATCH 1/3] dma-buf/dma-fence_array: use kvzalloc
Am 25.10.24 um 08:52 schrieb Friedrich Vock:
Quoted 5 lines · Matthew Brost
Quoted 4 lines · Christian König
Quoted 2 lines
Reports indicates that some userspace applications try to merge more than 80k of fences into a single
dma_fence_arrayleading to a warning from
Quoted 8 lines
Quoted 1 line
Really, yikes.
Not really IME. Unless Christian means some reports I don't have access to, the cases where userspace applications tried to do that were really just cases where the fence count exploded exponentially because
dma_fence_unwrap_mergefailed to actually merge identical fences (see patch 2). At no point have I actually seen apps trying to merge 80k+ unique fences.
While working on it I've modified our stress test tool to send the same 1GiB SDMA copy to 100k different contexts.
Turned out it's perfectly possible to create so many fences, there is nothing blocking userspace to do it.
While this isn't a realistic use case the kernel should at least not crash or spill a warning, but either handle or reject it gracefully.
Friedrich can you confirm that patch two in this series fixes the problem? I would really like to get it into drm-misc-fixes before 6.12 comes out.
Thanks,
Christian.
Quoted 61 lines
Regards,
FriedrichQuoted 56 lines
Quoted 10 lines
kzalloc()that the requested size becomes to big.While that is clearly an userspace bug we should probably handle that case gracefully in the kernel.
So we can either reject requests to merge more than a reasonable amount of fences (64k maybe?) or we can start to use
kvzalloc()instead ofkzalloc(). This patch here does the later.This patch seems reasonable to me if the above use is in fact valid.
Quoted 2 lines
Signed-off-by Christian König <[email protected]>Fixes tag?
Patch itself LGTM:
Reviewed-by Matthew Brost <[email protected]>Quoted 35 lines
---
drivers/dma-buf/dma-fence-array.c| 6 +++---1 file changed, 3 insertions(+), 3 deletions(-)drivers/dma-buf/dma-fence-array.c +2
-2@@ -119,8 +119,8 @@ static void dma_fence_array_release(struct dma_fence *fence) for (i = 0; i < array->num_fences; ++i) dma_fence_put(array->fences[i]); - kfree(array->fences); - dma_fence_free(fence); + kvfree(array->fences); + kvfree_rcu(fence, rcu); }static void dma_fence_array_set_deadline(struct
dma_fence*fence,drivers/dma-buf/dma-fence-array.c +1
-1@@ -153,7 +153,7 @@ struct dma_fence_array *dma_fence_array_alloc(int num_fences) { struct dma_fence_array *array; - return kzalloc(struct_size(array, callbacks, num_fences), GFP_KERNEL); + return kvzalloc(struct_size(array, callbacks, num_fences),GFP_KERNEL );}
EXPORT_SYMBOL(dma_fence_array_alloc);Signature · 1 line
2.34.1
Re: [PATCH 1/3] dma-buf/dma-fence_array: use kvzalloc
In reply to Christian KönigQuoted 10 lines · Christian König
Reports indicates that some userspace applications try to merge more than 80k of fences into a single
dma_fence_arrayleading to a warning fromkzalloc()that the requested size becomes to big.While that is clearly an userspace bug we should probably handle that case gracefully in the kernel.
So we can either reject requests to merge more than a reasonable amount of fences (64k maybe?) or we can start to use
kvzalloc()instead ofkzalloc(). This patch here does the later.
Rejecting would potentially be safer, otherwise there is a path for userspace to trigger a warn in kvmalloc_node (see 0829b5bcdd3b ("drm/i915: 2 GiB of relocations ought to be enough for anybody*")) and spam dmesg at will.
Question is what limit to set...
Regards,
Tvrtko
Quoted 30 lines
Signed-off-by Christian König <[email protected]>--- drivers/dma-buf/dma-fence-array.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)drivers/dma-buf/dma-fence-array.c +3
-3@@ -119,8 +119,8 @@ static void dma_fence_array_release(struct dma_fence *fence)for (i =0 ; i < array->num_fences; ++i)dma_fence_put (array->fences[i]); -kfree (array->fences); -dma_fence_free (fence); +kvfree (array->fences); +kvfree_rcu (fence, rcu); } static void dma_fence_array_set_deadline(struct dma_fence *fence,@@ -153,7 +153,7 @@ struct dma_fence_array *dma_fence_array_alloc(int num_fences) {struct dma_fence_array *array; -return kzalloc (struct_size (array, callbacks, num_fences),GFP_KERNEL ); +return kvzalloc (struct_size (array, callbacks, num_fences),GFP_KERNEL ); }EXPORT_SYMBOL (dma_fence_array_alloc);
Re: [PATCH 1/3] dma-buf/dma-fence_array: use kvzalloc
Quoted 6 lines · Tvrtko Ursulin
Quoted 4 lines · Christian König
Reports indicates that some userspace applications try to merge more than 80k of fences into a single
dma_fence_arrayleading to a warning fromkzalloc()that the requested size becomes to big.
Quoted 8 lines
Quoted 6 lines
While that is clearly an userspace bug we should probably handle that case gracefully in the kernel.
So we can either reject requests to merge more than a reasonable amount of fences (64k maybe?) or we can start to use
kvzalloc()instead ofkzalloc(). This patch here does the later.Rejecting would potentially be safer, otherwise there is a path for userspace to trigger a warn in
kvmalloc_node(see0829b5bcdd3b("drm/i915: 2 GiB of relocations ought to be enough for anybody*")) and spam dmesg at will.
Actually that is a WARN_ON_*ONCE* there so maybe not so critical to invent a limit. Up for discussion I suppose.
Regards,
Tvrtko
Quoted 37 lines
Question is what limit to set...
Regards,
Tvrtko
Quoted 30 lines
Signed-off-by Christian König <[email protected]>---
drivers/dma-buf/dma-fence-array.c| 6 +++---1 file changed, 3 insertions(+), 3 deletions(-)drivers/dma-buf/dma-fence-array.c +3
-3@@ -119,8 +119,8 @@ static void dma_fence_array_release(struct dma_fence *fence) for (i = 0; i < array->num_fences; ++i) dma_fence_put(array->fences[i]); - kfree(array->fences); - dma_fence_free(fence); + kvfree(array->fences); + kvfree_rcu(fence, rcu); } static void dma_fence_array_set_deadline(struct dma_fence *fence,@@ -153,7 +153,7 @@ struct dma_fence_array *dma_fence_array_alloc(int num_fences) { struct dma_fence_array *array; - return kzalloc(struct_size(array, callbacks, num_fences), GFP_KERNEL); + return kvzalloc(struct_size(array, callbacks, num_fences),GFP_KERNEL ); }
EXPORT_SYMBOL(dma_fence_array_alloc);
Re: [PATCH 1/3] dma-buf/dma-fence_array: use kvzalloc
Am 25.10.24 um 11:05 schrieb Tvrtko Ursulin:
Quoted 15 lines · Tvrtko Ursulin
Quoted 13 lines · Christian König
Quoted 10 lines
Reports indicates that some userspace applications try to merge more than 80k of fences into a single
dma_fence_arrayleading to a warning fromkzalloc()that the requested size becomes to big.While that is clearly an userspace bug we should probably handle that case gracefully in the kernel.
So we can either reject requests to merge more than a reasonable amount of fences (64k maybe?) or we can start to use
kvzalloc()instead ofkzalloc(). This patch here does the later.
Quoted 10 lines
Quoted 1 line
Rejecting would potentially be safer, otherwise there is a path for userspace to trigger a warn in
kvmalloc_node(see0829b5bcdd3b("drm/i915: 2 GiB of relocations ought to be enough for anybody*")) and spam dmesg at will.Actually that is a WARN_ON_*ONCE* there so maybe not so critical to invent a limit. Up for discussion I suppose.
Regards,
Tvrtko
Quoted 2 lines
Question is what limit to set...
That's one of the reasons why I opted for kvzalloc() initially.
I mean we could use some nice round number like 65536, but that would be totally arbitrary.
Any comments on the other two patches? I need to get them upstream.
Thanks,
Christian.
Quoted 35 lines
Quoted 35 lines
Regards,
Tvrtko
Quoted 30 lines
Signed-off-by Christian König <[email protected]>---
drivers/dma-buf/dma-fence-array.c| 6 +++---1 file changed, 3 insertions(+), 3 deletions(-)drivers/dma-buf/dma-fence-array.c +3
-3@@ -119,8 +119,8 @@ static void dma_fence_array_release(struct dma_fence *fence) for (i = 0; i < array->num_fences; ++i) dma_fence_put(array->fences[i]); - kfree(array->fences); - dma_fence_free(fence); + kvfree(array->fences); + kvfree_rcu(fence, rcu); } static void dma_fence_array_set_deadline(struct dma_fence *fence,@@ -153,7 +153,7 @@ struct dma_fence_array *dma_fence_array_alloc(int num_fences) { struct dma_fence_array *array; - return kzalloc(struct_size(array, callbacks, num_fences), GFP_KERNEL); + return kvzalloc(struct_size(array, callbacks, num_fences),GFP_KERNEL ); }
EXPORT_SYMBOL(dma_fence_array_alloc);
Re: [PATCH 1/3] dma-buf/dma-fence_array: use kvzalloc
Quoted 20 lines · Christian König
Am 25.10.24 um 11:05 schrieb Tvrtko Ursulin:
Quoted 19 lines · Tvrtko Ursulin
Quoted 6 lines · Christian König
Quoted 4 lines
Reports indicates that some userspace applications try to merge more than 80k of fences into a single
dma_fence_arrayleading to a warning fromkzalloc()that the requested size becomes to big.Quoted 8 lines
Quoted 6 lines
While that is clearly an userspace bug we should probably handle that case gracefully in the kernel.
So we can either reject requests to merge more than a reasonable amount of fences (64k maybe?) or we can start to use
kvzalloc()instead ofkzalloc(). This patch here does the later.Rejecting would potentially be safer, otherwise there is a path for userspace to trigger a warn in
kvmalloc_node(see0829b5bcdd3b("drm/i915: 2 GiB of relocations ought to be enough for anybody*")) and spam dmesg at will.Actually that is a WARN_ON_*ONCE* there so maybe not so critical to invent a limit. Up for discussion I suppose.
Quoted 8 lines
Quoted 6 lines
Regards,
Tvrtko
Quoted 2 lines
Question is what limit to set...
That's one of the reasons why I opted for
kvzalloc()initially.
I didn't get that, what was the reason? To not have to invent an arbitrary limit?
Quoted 1 line
I mean we could use some nice round number like 65536, but that would be totally arbitrary.
Yeah.. Set an arbitrary limit so a warning in __kvmalloc_node_noprof() is avoided? Or pass __GFP_NOWARN?
Quoted 1 line
Any comments on the other two patches? I need to get them upstream.
Will look into them shortly.
Regards,
Tvrtko
Quoted 39 lines
Thanks,
Christian.Quoted 35 lines
Quoted 35 lines
Regards,
Tvrtko
Quoted 30 lines
Signed-off-by Christian König <[email protected]>---
drivers/dma-buf/dma-fence-array.c| 6 +++---1 file changed, 3 insertions(+), 3 deletions(-)drivers/dma-buf/dma-fence-array.c +3
-3@@ -119,8 +119,8 @@ static void dma_fence_array_release(struct dma_fence *fence) for (i = 0; i < array->num_fences; ++i) dma_fence_put(array->fences[i]); - kfree(array->fences); - dma_fence_free(fence); + kvfree(array->fences); + kvfree_rcu(fence, rcu); } static void dma_fence_array_set_deadline(struct dma_fence *fence,@@ -153,7 +153,7 @@ struct dma_fence_array *dma_fence_array_alloc(int num_fences) { struct dma_fence_array *array; - return kzalloc(struct_size(array, callbacks, num_fences), GFP_KERNEL); + return kvzalloc(struct_size(array, callbacks, num_fences),GFP_KERNEL ); }
EXPORT_SYMBOL(dma_fence_array_alloc);
Re: [PATCH 1/3] dma-buf/dma-fence_array: use kvzalloc
Am 07.11.24 um 12:29 schrieb Tvrtko Ursulin:
Quoted 24 lines · Christian König
Quoted 22 lines
Am 25.10.24 um 11:05 schrieb Tvrtko Ursulin:
Quoted 21 lines · Tvrtko Ursulin
Quoted 6 lines · Christian König
Quoted 4 lines
Reports indicates that some userspace applications try to merge more than 80k of fences into a single
dma_fence_arrayleading to a warning fromkzalloc()that the requested size becomes to big.Quoted 8 lines
Quoted 6 lines
While that is clearly an userspace bug we should probably handle that case gracefully in the kernel.
So we can either reject requests to merge more than a reasonable amount of fences (64k maybe?) or we can start to use
kvzalloc()instead ofkzalloc(). This patch here does the later.Rejecting would potentially be safer, otherwise there is a path for userspace to trigger a warn in
kvmalloc_node(see0829b5bcdd3b("drm/i915: 2 GiB of relocations ought to be enough for anybody*")) and spam dmesg at will.Actually that is a WARN_ON_*ONCE* there so maybe not so critical to invent a limit. Up for discussion I suppose.
Regards,
Quoted 8 lines
Quoted 6 lines
Quoted 4 lines
Tvrtko
Quoted 2 lines
Question is what limit to set...
That's one of the reasons why I opted for
kvzalloc()initially.I didn't get that, what was the reason? To not have to invent an arbitrary limit?
Well that I couldn't come up with any arbitrary limit that I had confidence would work and not block real world use cases.
Switching to kvzalloc() just seemed the more defensive approach.
Quoted 4 lines
Quoted 2 lines
I mean we could use some nice round number like 65536, but that would be totally arbitrary.
Yeah.. Set an arbitrary limit so a warning in
__kvmalloc_node_noprof()is avoided? Or pass__GFP_NOWARN?
Well are we sure that will never hit 65536 in a real world use case? It's still pretty low.
Quoted 4 lines
Quoted 2 lines
Any comments on the other two patches? I need to get them upstream.
Will look into them shortly.
Thanks,
Christian.
Quoted 45 lines
Regards,
Tvrtko
Quoted 39 lines
Thanks,
Christian.Quoted 35 lines
Quoted 35 lines
Regards,
Tvrtko
Quoted 30 lines
Signed-off-by Christian König <[email protected]>---
drivers/dma-buf/dma-fence-array.c| 6 +++---1 file changed, 3 insertions(+), 3 deletions(-)drivers/dma-buf/dma-fence-array.c +3
-3@@ -119,8 +119,8 @@ static void dma_fence_array_release(struct dma_fence *fence) for (i = 0; i < array->num_fences; ++i) dma_fence_put(array->fences[i]); - kfree(array->fences); - dma_fence_free(fence); + kvfree(array->fences); + kvfree_rcu(fence, rcu); } static void dma_fence_array_set_deadline(struct dma_fence *fence,@@ -153,7 +153,7 @@ struct dma_fence_array *dma_fence_array_alloc(int num_fences) { struct dma_fence_array *array; - return kzalloc(struct_size(array, callbacks, num_fences), GFP_KERNEL); + return kvzalloc(struct_size(array, callbacks, num_fences),GFP_KERNEL ); }
EXPORT_SYMBOL(dma_fence_array_alloc);
Re: [PATCH 1/3] dma-buf/dma-fence_array: use kvzalloc
Quoted 30 lines · Christian König
Am 07.11.24 um 12:29 schrieb Tvrtko Ursulin:
Quoted 29 lines · Christian König
Quoted 27 lines
Am 25.10.24 um 11:05 schrieb Tvrtko Ursulin:
Quoted 25 lines · Tvrtko Ursulin
Quoted 6 lines · Christian König
Quoted 4 lines
Reports indicates that some userspace applications try to merge more than 80k of fences into a single
dma_fence_arrayleading to a warning fromkzalloc()that the requested size becomes to big.Quoted 8 lines
Quoted 6 lines
While that is clearly an userspace bug we should probably handle that case gracefully in the kernel.
So we can either reject requests to merge more than a reasonable amount of fences (64k maybe?) or we can start to use
kvzalloc()instead ofkzalloc(). This patch here does the later.Rejecting would potentially be safer, otherwise there is a path for userspace to trigger a warn in
kvmalloc_node(see0829b5bcdd3b("drm/i915: 2 GiB of relocations ought to be enough for anybody*")) and spam dmesg at will.Actually that is a WARN_ON_*ONCE* there so maybe not so critical to invent a limit. Up for discussion I suppose.
Regards,
Tvrtko
Quoted 2 lines
Question is what limit to set...
Quoted 7 lines
Quoted 3 lines
Quoted 1 line
That's one of the reasons why I opted for
kvzalloc()initially.I didn't get that, what was the reason? To not have to invent an arbitrary limit?
Well that I couldn't come up with any arbitrary limit that I had confidence would work and not block real world use cases.
Switching to
kvzalloc()just seemed the more defensive approach.
Yeah it is.
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
I mean we could use some nice round number like 65536, but that would be totally arbitrary.
Yeah.. Set an arbitrary limit so a warning in
__kvmalloc_node_noprof()is avoided? Or pass__GFP_NOWARN?Well are we sure that will never hit 65536 in a real world use case? It's still pretty low.
Ah no, I did not express myself clearly. I did not mean 64k, but a limit to align with INT_MAX __kvmalloc_node_noprof(). Or __GFP_NOWARN might be better when allocation size is userspace controlled.
Regards,
Tvrtko
Quoted 53 lines
Quoted 3 lines
Quoted 1 line
Any comments on the other two patches? I need to get them upstream.
Will look into them shortly.
Thanks,
Christian.Quoted 45 lines
Regards,
Tvrtko
Quoted 39 lines
Thanks,
Christian.Quoted 35 lines
Quoted 35 lines
Regards,
Tvrtko
Quoted 30 lines
Signed-off-by Christian König <[email protected]>---
drivers/dma-buf/dma-fence-array.c| 6 +++---1 file changed, 3 insertions(+), 3 deletions(-)drivers/dma-buf/dma-fence-array.c +3
-3@@ -119,8 +119,8 @@ static void dma_fence_array_release(struct dma_fence *fence) for (i = 0; i < array->num_fences; ++i) dma_fence_put(array->fences[i]); - kfree(array->fences); - dma_fence_free(fence); + kvfree(array->fences); + kvfree_rcu(fence, rcu); } static void dma_fence_array_set_deadline(struct dma_fence *fence,@@ -153,7 +153,7 @@ struct dma_fence_array *dma_fence_array_alloc(int num_fences) { struct dma_fence_array *array; - return kzalloc(struct_size(array, callbacks, num_fences), GFP_KERNEL); + return kvzalloc(struct_size(array, callbacks, num_fences),GFP_KERNEL ); }
EXPORT_SYMBOL(dma_fence_array_alloc);
PATCH 2/3 dma-buf: sort fences in dma_fence_unwrap_merge
In reply to Christian KönigThe merge function initially handled only individual fences and arrays which in turn were created by the merge function. This allowed to create the new array by a simple merge sort based on the fence context number.
The problem is now that since the addition of timeline sync objects userspace can create chain containers in basically any fence context order.
If those are merged together it can happen that we create really large arrays since the merge sort algorithm doesn't work any more.
So put an insert sort behind the merge sort which kicks in when the input fences are not in the expected order. This isn't as efficient as a heap sort, but has better properties for the most common use case.
--- drivers/dma-buf/dma-fence-unwrap.c | 39 ++++++++++++++++++++++++++---- 1 file changed, 34 insertions(+), 5 deletions(-)
drivers/dma-buf/dma-fence-unwrap.c +34 -5
@@ -106,7 +106,7 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, fences[i] =dma_fence_unwrap_first (fences[i], &iter[i]); count =0 ; - do { +while (true) {unsigned int sel; restart:
@@ -144,11 +144,40 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, } } -if (tmp) { - array[count++] =dma_fence_get (tmp); - fences[sel] =dma_fence_unwrap_next (&iter[sel]); +if (!tmp) +break ; + +/* +* We could use a binary search here, but since the assumption +* is that the main input are already sorted dma_fence_arrays +* just looking from end has a higher chance of finding the +* right location on the first try +*/ + +for (i = count; i--;) { +if (likely (array[i]->context < tmp->context)) +break ; + +if (array[i]->context == tmp->context) { +if (dma_fence_is_later (tmp, array[i])) { +dma_fence_put (array[i]); + array[i] =dma_fence_get (tmp); + } + fences[sel] =dma_fence_unwrap_next (&iter[sel]); + goto restart; + } } - }while (tmp); + + ++i; +/* +* Make room for the fence, this should be a nop most of the +* time. +*/ +memcpy (&array[i +1 ], &array[i], (count - i) *sizeof (*array)); + array[i] =dma_fence_get (tmp); + fences[sel] =dma_fence_unwrap_next (&iter[sel]); + count++; + };if (count ==0 ) { tmp =dma_fence_allocate_private_stub (ktime_get ());
Signature · 1 line
2.34.1
Re: [PATCH 2/3] dma-buf: sort fences in dma_fence_unwrap_merge
Quoted 43 lines · Christian König
The merge function initially handled only individual fences and arrays which in turn were created by the merge function. This allowed to create the new array by a simple merge sort based on the fence context number.
The problem is now that since the addition of timeline sync objects userspace can create chain containers in basically any fence context order.
If those are merged together it can happen that we create really large arrays since the merge sort algorithm doesn't work any more.
So put an insert sort behind the merge sort which kicks in when the input fences are not in the expected order. This isn't as efficient as a heap sort, but has better properties for the most common use case.
Signed-off-by Christian König <[email protected]>--- drivers/dma-buf/dma-fence-unwrap.c | 39 ++++++++++++++++++++++++++---- 1 file changed, 34 insertions(+), 5 deletions(-)drivers/dma-buf/dma-fence-unwrap.c +2
-4@@ -106,7 +106,7 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, fences[i] =dma_fence_unwrap_first (fences[i], &iter[i]); count =0 ; - do { +while (true) {unsigned int sel; restart:@@ -144,11 +144,40 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, } } -if (tmp) { - array[count++] =dma_fence_get (tmp); - fences[sel] =dma_fence_unwrap_next (&iter[sel]); +if (!tmp)
drivers/dma-buf/dma-fence-unwrap.c struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, · line 157
Quoted 10 lines
drivers/dma-buf/dma-fence-unwrap.c +10
-0+break ; + +/* +* We could use a binary search here, but since the assumption +* is that the main input are already sorted dma_fence_arrays +* just looking from end has a higher chance of finding the +* right location on the first try +*/ + +for (i = count; i--;) {
This is broken. The first iteration of this loop will always index out of bounds. What you probably want here is:
+ for (i = count - 1; count && i--;) {
This intentionally overflows for count == 0, but the ++i after the loop undoes that. Maybe it would be worth a comment to point out that's intentional.
Quoted 10 lines
drivers/dma-buf/dma-fence-unwrap.c +10
-0+if (likely (array[i]->context < tmp->context)) +break ; + +if (array[i]->context == tmp->context) { +if (dma_fence_is_later (tmp, array[i])) { +dma_fence_put (array[i]); + array[i] =dma_fence_get (tmp); + } + fences[sel] =dma_fence_unwrap_next (&iter[sel]); + goto restart;
drivers/dma-buf/dma-fence-unwrap.c struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, · line 176
Quoted 10 lines
drivers/dma-buf/dma-fence-unwrap.c +8
-1+ } } - }while (tmp); + + ++i; +/* +* Make room for the fence, this should be a nop most of the +* time. +*/ +memcpy (&array[i +1 ], &array[i], (count - i) *sizeof (*array));
Need memmove here, src and dst alias.
I took it for a spin with these things fixed and it seemed to resolve the issue as well. How do you want to proceed? I guess I would be comfortable putting a Reviewed-by and/or Tested-by on a version with these things fixed (with the usual caveat that I'm not a maintainer - I guess the process requires (at least one) reviewer to be?).
By the way, I guess you might've had some internal branches where this fix needed to go into quick or something? Usually I'm happy to make a v2 for my patches myself, too ;)
Regards,
Friedrich
Quoted 7 lines
drivers/dma-buf/dma-fence-unwrap.c +4
-0+ array[i] =dma_fence_get (tmp); + fences[sel] =dma_fence_unwrap_next (&iter[sel]); + count++; + };if (count ==0 ) { tmp =dma_fence_allocate_private_stub (ktime_get ());
Re: [PATCH 2/3] dma-buf: sort fences in dma_fence_unwrap_merge
Am 30.10.24 um 19:10 schrieb Friedrich Vock:
Quoted 51 lines · Christian König
Quoted 50 lines
The merge function initially handled only individual fences and arrays which in turn were created by the merge function. This allowed to create the new array by a simple merge sort based on the fence context number.
The problem is now that since the addition of timeline sync objects userspace can create chain containers in basically any fence context order.
If those are merged together it can happen that we create really large arrays since the merge sort algorithm doesn't work any more.
So put an insert sort behind the merge sort which kicks in when the input fences are not in the expected order. This isn't as efficient as a heap sort, but has better properties for the most common use case.
Signed-off-by Christian König <[email protected]>---
drivers/dma-buf/dma-fence-unwrap.c| 39 ++++++++++++++++++++++++++----1 file changed, 34 insertions(+), 5 deletions(-)drivers/dma-buf/dma-fence-unwrap.c +1
-1@@ -106,7 +106,7 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, fences[i] = dma_fence_unwrap_first(fences[i], &iter[i]); count = 0; - do { + while (true) { unsigned int sel;restart:
drivers/dma-buf/dma-fence-unwrap.c +6
-3@@ -144,11 +144,40 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, } } - if (tmp) { - array[count++] = dma_fence_get(tmp); - fences[sel] = dma_fence_unwrap_next(&iter[sel]); + if (!tmp) + break; + + /* + * We could use a binary search here, but since the assumption + * is that the main input are already sorted dma_fence_arrays
Quoted 8 lines
drivers/dma-buf/dma-fence-unwrap.c struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, · line 157
Quoted 5 lines
drivers/dma-buf/dma-fence-unwrap.c +5
-0+* just looking from end has a higher chance of finding the +* right location on the first try +*/ + + for (i = count; i--;) {This is broken. The first iteration of this loop will always index out of bounds.
Nope, that is correct. The condition is evaluated before the loop, so the i-- reduces the index to the last element in the array.
Regards,
Christian.
Quoted 52 lines
What you probably want here is:
+ for (i = count - 1; count && i--;) {
This intentionally overflows for count == 0, but the ++i after the loop undoes that. Maybe it would be worth a comment to point out that's intentional.
Quoted 10 lines
drivers/dma-buf/dma-fence-unwrap.c +10
-0+ if (likely(array[i]->context < tmp->context)) + break; + + if (array[i]->context == tmp->context) { + if (dma_fence_is_later(tmp, array[i])) { + dma_fence_put(array[i]); + array[i] = dma_fence_get(tmp); + } + fences[sel] = dma_fence_unwrap_next(&iter[sel]); + goto restart;drivers/dma-buf/dma-fence-unwrap.c struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, · line 176
Quoted 10 lines
drivers/dma-buf/dma-fence-unwrap.c +8
-1+ } } - } while (tmp); + + ++i; + /* + * Make room for the fence, this should be a nop most of the + * time. + */ + memcpy(&array[i + 1], &array[i], (count - i) * sizeof(*array));Need memmove here, src and dst alias.
I took it for a spin with these things fixed and it seemed to resolve the issue as well. How do you want to proceed? I guess I would be comfortable putting a Reviewed-by and/or Tested-by on a version with these things fixed (with the usual caveat that I'm not a maintainer - I guess the process requires (at least one) reviewer to be?).
By the way, I guess you might've had some internal branches where this fix needed to go into quick or something? Usually I'm happy to make a v2 for my patches myself, too ;)
Regards,
FriedrichQuoted 7 lines
drivers/dma-buf/dma-fence-unwrap.c +4
-0+ array[i] = dma_fence_get(tmp); + fences[sel] = dma_fence_unwrap_next(&iter[sel]); + count++; + }; if (count == 0) {tmp = dma_fence_allocate_private_stub(ktime_get());
Re: [PATCH 2/3] dma-buf: sort fences in dma_fence_unwrap_merge
In reply to Christian KönigQuoted 66 lines · Christian König
The merge function initially handled only individual fences and arrays which in turn were created by the merge function. This allowed to create the new array by a simple merge sort based on the fence context number.
The problem is now that since the addition of timeline sync objects userspace can create chain containers in basically any fence context order.
If those are merged together it can happen that we create really large arrays since the merge sort algorithm doesn't work any more.
So put an insert sort behind the merge sort which kicks in when the input fences are not in the expected order. This isn't as efficient as a heap sort, but has better properties for the most common use case.
Signed-off-by Christian König <[email protected]>--- drivers/dma-buf/dma-fence-unwrap.c | 39 ++++++++++++++++++++++++++---- 1 file changed, 34 insertions(+), 5 deletions(-)drivers/dma-buf/dma-fence-unwrap.c +23
-5@@ -106,7 +106,7 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, fences[i] =dma_fence_unwrap_first (fences[i], &iter[i]); count =0 ; - do { +while (true) {unsigned int sel; restart:@@ -144,11 +144,40 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, } } -if (tmp) { - array[count++] =dma_fence_get (tmp); - fences[sel] =dma_fence_unwrap_next (&iter[sel]); +if (!tmp) +break ; + +/* +* We could use a binary search here, but since the assumption +* is that the main input are already sorted dma_fence_arrays +* just looking from end has a higher chance of finding the +* right location on the first try +*/ + +for (i = count; i--;) { +if (likely (array[i]->context < tmp->context)) +break ; + +if (array[i]->context == tmp->context) { +if (dma_fence_is_later (tmp, array[i])) { +dma_fence_put (array[i]); + array[i] =dma_fence_get (tmp); + } + fences[sel] =dma_fence_unwrap_next (&iter[sel]); + goto restart; + } } - }while (tmp);
drivers/dma-buf/dma-fence-unwrap.c struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, · line 179
Quoted 10 lines
drivers/dma-buf/dma-fence-unwrap.c +10
-0+ + ++i; +/* +* Make room for the fence, this should be a nop most of the +* time. +*/ +memcpy (&array[i +1 ], &array[i], (count - i) *sizeof (*array)); + array[i] =dma_fence_get (tmp); + fences[sel] =dma_fence_unwrap_next (&iter[sel]); + count++;
Having ventured into this function for the first time, I can say that this is some smart code which is not easy to grasp. It could definitely benefit from a high level comment before the do-while loop to explain what it is going to do.
Next and tmp local variable names I also wonder if could be renamed to something more descriptive.
And the algorithmic complexity of the end result, given the multiple loops and gotos, I have no idea what it could be.
Has a dumb solution been considered like a two-pass with a pessimistically allocated fence array been considered? Like:
1) Populate array with all unsignalled unwrapped fences. (O(count))
2) Bog standard include/linux/sort.h by context and seqno. (O(count*log (count)))
3) Walk array and squash same context to latest fence. (Before this patch that wasn't there, right?). (O(count)) (Overwrite in place, no memcpy needed.)
Algorithmic complexity of that would be obvious and code much simpler.
Regards,
Tvrtko
Quoted 4 lines
drivers/dma-buf/dma-fence-unwrap.c +1
-0+ };if (count ==0 ) { tmp =dma_fence_allocate_private_stub (ktime_get ());
Re: [PATCH 2/3] dma-buf: sort fences in dma_fence_unwrap_merge
Quoted 86 lines · Tvrtko Ursulin
Quoted 65 lines · Christian König
The merge function initially handled only individual fences and arrays which in turn were created by the merge function. This allowed to create the new array by a simple merge sort based on the fence context number.
The problem is now that since the addition of timeline sync objects userspace can create chain containers in basically any fence context order.
If those are merged together it can happen that we create really large arrays since the merge sort algorithm doesn't work any more.
So put an insert sort behind the merge sort which kicks in when the input fences are not in the expected order. This isn't as efficient as a heap sort, but has better properties for the most common use case.
Signed-off-by Christian König <[email protected]>---
drivers/dma-buf/dma-fence-unwrap.c| 39 ++++++++++++++++++++++++++----1 file changed, 34 insertions(+), 5 deletions(-)drivers/dma-buf/dma-fence-unwrap.c +1
-1@@ -106,7 +106,7 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, fences[i] = dma_fence_unwrap_first(fences[i], &iter[i]); count = 0; - do { + while (true) { unsigned int sel;restart:
drivers/dma-buf/dma-fence-unwrap.c +22
-4@@ -144,11 +144,40 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, } } - if (tmp) { - array[count++] = dma_fence_get(tmp); - fences[sel] = dma_fence_unwrap_next(&iter[sel]); + if (!tmp) + break; + + /* + * We could use a binary search here, but since the assumption + * is that the main input are already sorted dma_fence_arrays + * just looking from end has a higher chance of finding the + * right location on the first try + */ + + for (i = count; i--;) { + if (likely(array[i]->context < tmp->context)) + break; + + if (array[i]->context == tmp->context) { + if (dma_fence_is_later(tmp, array[i])) { + dma_fence_put(array[i]); + array[i] = dma_fence_get(tmp); + } + fences[sel] = dma_fence_unwrap_next(&iter[sel]); + goto restart; + } } - } while (tmp);drivers/dma-buf/dma-fence-unwrap.c struct dma_fence · line 179
Quoted 10 lines
drivers/dma-buf/dma-fence-unwrap.c +10
-0+ + ++i; + /* + * Make room for the fence, this should be a nop most of the + * time. + */ + memcpy(&array[i + 1], &array[i], (count - i) * sizeof(*array)); + array[i] = dma_fence_get(tmp); + fences[sel] = dma_fence_unwrap_next(&iter[sel]); + count++;Having ventured into this function for the first time, I can say that this is some smart code which is not easy to grasp. It could definitely benefit from a high level comment before the do-while loop to explain what it is going to do.
Next and tmp local variable names I also wonder if could be renamed to something more descriptive.
And the algorithmic complexity of the end result, given the multiple loops and gotos, I have no idea what it could be.
Has a dumb solution been considered like a two-pass with a pessimistically allocated fence array been considered? Like:
Quoted 7 lines
1) Populate array with all unsignalled unwrapped fences. (O(count))
2) Bog standard
include/linux/sort.hby context and seqno. (O(count*log (count)))3) Walk array and squash same context to latest fence. (Before this patch that wasn't there, right?). (O(count)) (Overwrite in place, no memcpy needed.)
Algorithmic complexity of that would be obvious and code much simpler.
FWIW something like the below passes selftests. How does it look to you? Do you think more or less efficient and more or less readable?
commit 8a7c3ea7e7af85e813bf5fc151537ae37be1d6d9
Author: Tvrtko Ursulin <[email protected]> Date: Fri Nov 8 10:14:15 2024 +0000
__dma_fence_unwrap_merge
drivers/dma-buf/dma-fence-unwrap.c +53 -52
@@ -12,6 +12,7 @@#include <linux/dma-fence-chain.h> #include <linux/dma-fence-unwrap.h> #include <linux/slab.h> +#include <linux/sort.h> /* Internal helper to start new array iteration, don't use directly */ static struct dma_fence *
@@ -59,17 +60,39 @@ struct dma_fence *dma_fence_unwrap_next(struct dma_fence_unwrap *cursor) }EXPORT_SYMBOL_GPL (dma_fence_unwrap_next); + +static int fence_cmp (const void *_a,const void *_b) +{ +const struct dma_fence *a = *(const struct dma_fence **)_a; +const struct dma_fence *b = *(const struct dma_fence **)_b; + +if (a->context < b->context) +return -1 ; +else if (a->context > b->context) +return 1 ; + +if (a->seqno < b->seqno) +return -1 ; +else if (a->seqno > b->seqno) +return 1 ; + +return 0 ; +} +/* Implementation for the dma_fence_merge() marco, don't use directly */ struct dma_fence *__dma_fence_unwrap_merge (unsigned int num_fences,struct dma_fence **fences,struct dma_fence_unwrap *iter) { -struct dma_fence_array *result;struct dma_fence *tmp, **array; +struct dma_fence_array *result;ktime_t timestamp; -unsigned int i; -size_t count; +int i, j, count; +/* +* Count number of unwrapped fences and fince the latest signaled +* timestamp. +*/ count =0 ; timestamp =ns_to_ktime (0 );for (i =0 ; i < num_fences; ++i) {
@@ -92,63 +115,41 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences,if (count ==0 )return dma_fence_allocate_private_stub (timestamp); +/* +* Allocate and populate the array. +*/ array =kmalloc_array (count,sizeof (*array),GFP_KERNEL );if (!array)return NULL ; -/* -* This trashes the input fence array and uses it as position for the -* following merge loop. This works because the dma_fence_merge() -* wrapper macro is creating this temporary array on the stack together -* with the iterators. -*/ -for (i =0 ; i < num_fences; ++i) - fences[i] =dma_fence_unwrap_first (fences[i], &iter[i]); - count =0 ; -do { -unsigned int sel; - -restart: - tmp =NULL ; -for (i =0 ; i < num_fences; ++i) { -struct dma_fence *next; - -while (fences[i] &&dma_fence_is_signaled (fences[i])) - fences[i] =dma_fence_unwrap_next (&iter[i]); - - next = fences[i]; -if (!next) -continue ; - -/* -* We can't guarantee that inpute fences are ordered by -* context, but it is still quite likely when this -* function is used multiple times. So attempt to order -* the fences by context as we pass over them and merge -* fences with the same context. -*/ -if (!tmp || tmp->context > next->context) { - tmp = next; - sel = i; - - }else if (tmp->context < next->context) { -continue ; - - }else if (dma_fence_is_later (tmp, next)) { - fences[i] =dma_fence_unwrap_next (&iter[i]); - goto restart; - }else { - fences[sel] =dma_fence_unwrap_next (&iter[sel]); - goto restart; - } +for (i =0 ; i < num_fences; ++i) { +dma_fence_unwrap_for_each (tmp, &iter[i], fences[i]) { +if (!dma_fence_is_signaled (tmp)) + array[count++] = tmp; } + } + +/* +* Sort in context and seqno order. +*/ +sort (array, count,sizeof (*array), fence_cmp,NULL ); -if (tmp) { - array[count++] =dma_fence_get (tmp); - fences[sel] =dma_fence_unwrap_next (&iter[sel]); +/* +* Only keep the most recent fence for each context. +*/ + j =0 ; + tmp = array[0 ]; +for (i =1 ; i < count; i++) { +if (array[i]->context != tmp->context) { + array[j++] =dma_fence_get (tmp); } - }while (tmp); + tmp = array[i]; + } +if (tmp->context != array[j -1 ]->context) { + array[j++] =dma_fence_get (tmp); + } + count = j;if (count ==0 ) { tmp =dma_fence_allocate_private_stub (ktime_get ());
Regards,
Tvrtko
Quoted 8 lines
Regards,
Tvrtko
Quoted 3 lines
drivers/dma-buf/dma-fence-unwrap.c +1
-0+ }; if (count == 0) { tmp = dma_fence_allocate_private_stub(ktime_get());
Re: [PATCH 2/3] dma-buf: sort fences in dma_fence_unwrap_merge
Am 08.11.24 um 12:22 schrieb Tvrtko Ursulin:
Quoted 90 lines · Tvrtko Ursulin
Quoted 89 lines · Christian König
Quoted 67 lines
The merge function initially handled only individual fences and arrays which in turn were created by the merge function. This allowed to create the new array by a simple merge sort based on the fence context number.
The problem is now that since the addition of timeline sync objects userspace can create chain containers in basically any fence context order.
If those are merged together it can happen that we create really large arrays since the merge sort algorithm doesn't work any more.
So put an insert sort behind the merge sort which kicks in when the input fences are not in the expected order. This isn't as efficient as a heap sort, but has better properties for the most common use case.
Signed-off-by Christian König <[email protected]>---
drivers/dma-buf/dma-fence-unwrap.c| 39
++++++++++++++++++++++++++----1 file changed, 34 insertions(+), 5 deletions(-)drivers/dma-buf/dma-fence-unwrap.c +1
-1@@ -106,7 +106,7 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, fences[i] = dma_fence_unwrap_first(fences[i], &iter[i]); count = 0; - do { + while (true) { unsigned int sel;restart:
drivers/dma-buf/dma-fence-unwrap.c +23
-4@@ -144,11 +144,40 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, } } - if (tmp) { - array[count++] = dma_fence_get(tmp); - fences[sel] = dma_fence_unwrap_next(&iter[sel]); + if (!tmp) + break; + + /* + * We could use a binary search here, but since the assumption + * is that the main input are already sorted dma_fence_arrays + * just looking from end has a higher chance of finding the + * right location on the first try + */ + + for (i = count; i--;) { + if (likely(array[i]->context < tmp->context)) + break; + + if (array[i]->context == tmp->context) { + if (dma_fence_is_later(tmp, array[i])) { + dma_fence_put(array[i]); + array[i] = dma_fence_get(tmp); + } + fences[sel] = dma_fence_unwrap_next(&iter[sel]); + goto restart; + } } - } while (tmp); +drivers/dma-buf/dma-fence-unwrap.c struct dma_fence · line 180
Quoted 10 lines
drivers/dma-buf/dma-fence-unwrap.c +9
-0+ ++i; + /* + * Make room for the fence, this should be a nop most of the + * time. + */ + memcpy(&array[i + 1], &array[i], (count - i) *sizeof (*array)); + array[i] = dma_fence_get(tmp); + fences[sel] = dma_fence_unwrap_next(&iter[sel]); + count++;Having ventured into this function for the first time, I can say that this is some smart code which is not easy to grasp. It could definitely benefit from a high level comment before the do-while loop to explain what it is going to do.
Next and tmp local variable names I also wonder if could be renamed to something more descriptive.
And the algorithmic complexity of the end result, given the multiple loops and gotos, I have no idea what it could be.
Has a dumb solution been considered like a two-pass with a pessimistically allocated fence array been considered? Like:
1) Populate array with all unsignalled unwrapped fences. (O(count))
Quoted 7 lines
Quoted 5 lines
2) Bog standard
include/linux/sort.hby context and seqno. (O(count*log (count)))3) Walk array and squash same context to latest fence. (Before this patch that wasn't there, right?). (O(count)) (Overwrite in place, no memcpy needed.)
Algorithmic complexity of that would be obvious and code much simpler.
FWIW something like the below passes selftests. How does it look to you? Do you think more or less efficient and more or less readable?
Yeah I was considering the exact same thing.
What hold me back was the fact that the heap sort() implementation is really inefficient for the most common use case of this. In other words two arrays with fences already sorted is basically just O(count).
And I'm also not sure how many fences we see in those arrays in practice. With Vulkan basically trying to feed multiple contexts to keep all CPUs busy we might have quite a number here.
Regards,
Christian.
Quoted 174 lines
commit
8a7c3ea7e7af85e813bf5fc151537ae37be1d6d9
Author: Tvrtko Ursulin <[email protected]> Date: Fri Nov 8 10:14:15 2024 +0000
__dma_fence_unwrap_mergeSigned-off-by Tvrtko Ursulin <[email protected]>drivers/dma-buf/dma-fence-unwrap.c +1
-0@@ -12,6 +12,7 @@ #include <linux/dma-fence-chain.h> #include <linux/dma-fence-unwrap.h> #include <linux/slab.h> +#include <linux/sort.h> /* Internal helper to start new array iteration, don't use directly */static struct
dma_fence*drivers/dma-buf/dma-fence-unwrap.c +25
-3@@ -59,17 +60,39 @@ struct dma_fence *dma_fence_unwrap_next(struct dma_fence_unwrap *cursor) } EXPORT_SYMBOL_GPL(dma_fence_unwrap_next); + +static int fence_cmp (const void *_a,const void *_b) +{ + const struct dma_fence *a = *(const struct dma_fence **)_a; + const struct dma_fence *b = *(const struct dma_fence **)_b; + + if (a->context < b->context) + return -1; + else if (a->context > b->context) + return 1; + + if (a->seqno < b->seqno) + return -1; + else if (a->seqno > b->seqno) + return 1; + + return 0; +} + /* Implementation for the dma_fence_merge() marco, don't use directly */ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, struct dma_fence **fences, struct dma_fence_unwrap *iter) { - struct dma_fence_array *result; struct dma_fence *tmp, **array; + struct dma_fence_array *result; ktime_t timestamp; - unsigned int i; - size_t count; + int i, j, count; + /* + * Count number of unwrapped fences and fince the latest signaled + * timestamp. + */ count = 0; timestamp = ns_to_ktime(0);for (i = 0; i <
num_fences; ++i) {drivers/dma-buf/dma-fence-unwrap.c +3
-2@@ -92,63 +115,41 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, if (count == 0) return dma_fence_allocate_private_stub(timestamp); + /* + * Allocate and populate the array. + */ array = kmalloc_array(count, sizeof(*array), GFP_KERNEL); if (!array) return NULL; - /* -* This trashes the input fence array and uses it as position for the
- * following merge loop. This works because thedma_fence_merge()- * wrapper macro is creating this temporary array on the stack together
- * with the iterators.
- */
- for (i = 0; i <num_fences; ++i)
- fences[i] =dma_fence_unwrap_first(fences[i], &iter[i]); -
count = 0;
- do {
- unsigned int sel;drivers/dma-buf/dma-fence-unwrap.c +4
-34- -restart: - tmp = NULL; - for (i = 0; i < num_fences; ++i) { - struct dma_fence *next; - - while (fences[i] && dma_fence_is_signaled(fences[i])) - fences[i] = dma_fence_unwrap_next(&iter[i]); - - next = fences[i]; - if (!next) - continue; - - /* - * We can't guarantee that inpute fences are ordered by - * context, but it is still quite likely when this - * function is used multiple times. So attempt to order - * the fences by context as we pass over them and merge - * fences with the same context. - */ - if (!tmp || tmp->context > next->context) { - tmp = next; - sel = i; - - } else if (tmp->context < next->context) { - continue; - - } else if (dma_fence_is_later(tmp, next)) { - fences[i] = dma_fence_unwrap_next(&iter[i]); - goto restart; - } else { - fences[sel] = dma_fence_unwrap_next(&iter[sel]); - goto restart; - } + for (i = 0; i < num_fences; ++i) { + dma_fence_unwrap_for_each(tmp, &iter[i], fences[i]) { + if (!dma_fence_is_signaled(tmp)) + array[count++] = tmp;}
+ }
+
+ /*
+ * Sort in context and seqno order.
+ */
+sort(array, count, sizeof(*array), fence_cmp, NULL);- if (tmp) {
- array[count++] =dma_fence_get(tmp);
- fences[sel] =dma_fence_unwrap_next(&iter[sel]); + /*
+ * Only keep the most recent fence for each context. + */
+ j = 0;
+ tmp = array[0];
+ for (i = 1; i < count; i++) {
+ if (array[i]->context !=tmp->context) {
+ array[j++] =dma_fence_get(tmp);
}
- } while (tmp);
+ tmp = array[i];
+ }
+ if (tmp->context!= array[j - 1]->context) {
+ array[j++] =dma_fence_get(tmp);
+ }
+ count = j;if (count == 0) {
tmp = dma_fence_allocate_private_stub(ktime_get());Regards,
Tvrtko
Quoted 8 lines
Regards,
Tvrtko
Quoted 3 lines
drivers/dma-buf/dma-fence-unwrap.c +1
-0+ }; if (count == 0) { tmp = dma_fence_allocate_private_stub(ktime_get());
Re: [PATCH 2/3] dma-buf: sort fences in dma_fence_unwrap_merge
Quoted 97 lines · Christian König
Am 08.11.24 um 12:22 schrieb Tvrtko Ursulin:
Quoted 96 lines · Tvrtko Ursulin
Quoted 94 lines · Christian König
Quoted 67 lines
The merge function initially handled only individual fences and arrays which in turn were created by the merge function. This allowed to create the new array by a simple merge sort based on the fence context number.
The problem is now that since the addition of timeline sync objects userspace can create chain containers in basically any fence context order.
If those are merged together it can happen that we create really large arrays since the merge sort algorithm doesn't work any more.
So put an insert sort behind the merge sort which kicks in when the input fences are not in the expected order. This isn't as efficient as a heap sort, but has better properties for the most common use case.
Signed-off-by Christian König <[email protected]>---
drivers/dma-buf/dma-fence-unwrap.c| 39
++++++++++++++++++++++++++----1 file changed, 34 insertions(+), 5 deletions(-)drivers/dma-buf/dma-fence-unwrap.c +1
-1@@ -106,7 +106,7 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, fences[i] = dma_fence_unwrap_first(fences[i], &iter[i]); count = 0; - do { + while (true) { unsigned int sel;restart:
drivers/dma-buf/dma-fence-unwrap.c +23
-4@@ -144,11 +144,40 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, } } - if (tmp) { - array[count++] = dma_fence_get(tmp); - fences[sel] = dma_fence_unwrap_next(&iter[sel]); + if (!tmp) + break; + + /* + * We could use a binary search here, but since the assumption + * is that the main input are already sorted dma_fence_arrays + * just looking from end has a higher chance of finding the + * right location on the first try + */ + + for (i = count; i--;) { + if (likely(array[i]->context < tmp->context)) + break; + + if (array[i]->context == tmp->context) { + if (dma_fence_is_later(tmp, array[i])) { + dma_fence_put(array[i]); + array[i] = dma_fence_get(tmp); + } + fences[sel] = dma_fence_unwrap_next(&iter[sel]); + goto restart; + } } - } while (tmp); +drivers/dma-buf/dma-fence-unwrap.c struct dma_fence · line 180
Quoted 10 lines
drivers/dma-buf/dma-fence-unwrap.c +9
-0+ ++i; + /* + * Make room for the fence, this should be a nop most of the + * time. + */ + memcpy(&array[i + 1], &array[i], (count - i) *sizeof (*array)); + array[i] = dma_fence_get(tmp); + fences[sel] = dma_fence_unwrap_next(&iter[sel]); + count++;Having ventured into this function for the first time, I can say that this is some smart code which is not easy to grasp. It could definitely benefit from a high level comment before the do-while loop to explain what it is going to do.
Next and tmp local variable names I also wonder if could be renamed to something more descriptive.
And the algorithmic complexity of the end result, given the multiple loops and gotos, I have no idea what it could be.
Has a dumb solution been considered like a two-pass with a pessimistically allocated fence array been considered? Like:
1) Populate array with all unsignalled unwrapped fences. (O(count))
2) Bog standard
include/linux/sort.hby context and seqno. (O(count*log (count)))3) Walk array and squash same context to latest fence. (Before this patch that wasn't there, right?). (O(count)) (Overwrite in place, no memcpy needed.)
Algorithmic complexity of that would be obvious and code much simpler.
Quoted 7 lines
Quoted 1 line
FWIW something like the below passes selftests. How does it look to you? Do you think more or less efficient and more or less readable?
Yeah I was considering the exact same thing.
What hold me back was the fact that the heap
sort()implementation is really inefficient for the most common use case of this. In other words two arrays with fences already sorted is basically just O(count).And I'm also not sure how many fences we see in those arrays in practice. With Vulkan basically trying to feed multiple contexts to keep all CPUs busy we might have quite a number here.
I can add some instrumentation and run some games next week.
Another option is adding the sort algorithm you want with the same API as kernel's sort. Even if a local implementation that may already increase readability of the merging process.
Regards,
Tvrtko
Quoted 179 lines
Regards,
Christian.Quoted 174 lines
commit
8a7c3ea7e7af85e813bf5fc151537ae37be1d6d9
Author: Tvrtko Ursulin <[email protected]> Date: Fri Nov 8 10:14:15 2024 +0000
__dma_fence_unwrap_mergeSigned-off-by Tvrtko Ursulin <[email protected]>drivers/dma-buf/dma-fence-unwrap.c +1
-0@@ -12,6 +12,7 @@ #include <linux/dma-fence-chain.h> #include <linux/dma-fence-unwrap.h> #include <linux/slab.h> +#include <linux/sort.h> /* Internal helper to start new array iteration, don't use directly */static struct
dma_fence*drivers/dma-buf/dma-fence-unwrap.c +25
-3@@ -59,17 +60,39 @@ struct dma_fence *dma_fence_unwrap_next(struct dma_fence_unwrap *cursor) } EXPORT_SYMBOL_GPL(dma_fence_unwrap_next); + +static int fence_cmp (const void *_a,const void *_b) +{ + const struct dma_fence *a = *(const struct dma_fence **)_a; + const struct dma_fence *b = *(const struct dma_fence **)_b; + + if (a->context < b->context) + return -1; + else if (a->context > b->context) + return 1; + + if (a->seqno < b->seqno) + return -1; + else if (a->seqno > b->seqno) + return 1; + + return 0; +} + /* Implementation for the dma_fence_merge() marco, don't use directly */ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, struct dma_fence **fences, struct dma_fence_unwrap *iter) { - struct dma_fence_array *result; struct dma_fence *tmp, **array; + struct dma_fence_array *result; ktime_t timestamp; - unsigned int i; - size_t count; + int i, j, count; + /* + * Count number of unwrapped fences and fince the latest signaled + * timestamp. + */ count = 0; timestamp = ns_to_ktime(0);for (i = 0; i <
num_fences; ++i) {drivers/dma-buf/dma-fence-unwrap.c +3
-2@@ -92,63 +115,41 @@ struct dma_fence *__dma_fence_unwrap_merge(unsigned int num_fences, if (count == 0) return dma_fence_allocate_private_stub(timestamp); + /* + * Allocate and populate the array. + */ array = kmalloc_array(count, sizeof(*array), GFP_KERNEL); if (!array) return NULL; - /* -* This trashes the input fence array and uses it as position for the
- * following merge loop. This works because thedma_fence_merge()- * wrapper macro is creating this temporary array on the stack together
- * with the iterators.
- */
- for (i = 0; i <num_fences; ++i)
- fences[i] =dma_fence_unwrap_first(fences[i], &iter[i]); -
count = 0;
- do {
- unsigned int sel;drivers/dma-buf/dma-fence-unwrap.c +4
-34- -restart: - tmp = NULL; - for (i = 0; i < num_fences; ++i) { - struct dma_fence *next; - - while (fences[i] && dma_fence_is_signaled(fences[i])) - fences[i] = dma_fence_unwrap_next(&iter[i]); - - next = fences[i]; - if (!next) - continue; - - /* - * We can't guarantee that inpute fences are ordered by - * context, but it is still quite likely when this - * function is used multiple times. So attempt to order - * the fences by context as we pass over them and merge - * fences with the same context. - */ - if (!tmp || tmp->context > next->context) { - tmp = next; - sel = i; - - } else if (tmp->context < next->context) { - continue; - - } else if (dma_fence_is_later(tmp, next)) { - fences[i] = dma_fence_unwrap_next(&iter[i]); - goto restart; - } else { - fences[sel] = dma_fence_unwrap_next(&iter[sel]); - goto restart; - } + for (i = 0; i < num_fences; ++i) { + dma_fence_unwrap_for_each(tmp, &iter[i], fences[i]) { + if (!dma_fence_is_signaled(tmp)) + array[count++] = tmp;}
+ }
+
+ /*
+ * Sort in context and seqno order.
+ */
+sort(array, count, sizeof(*array), fence_cmp, NULL);- if (tmp) {
- array[count++] =dma_fence_get(tmp);
- fences[sel] =dma_fence_unwrap_next(&iter[sel]); + /*
+ * Only keep the most recent fence for each context. + */
+ j = 0;
+ tmp = array[0];
+ for (i = 1; i < count; i++) {
+ if (array[i]->context !=tmp->context) {
+ array[j++] =dma_fence_get(tmp);
}
- } while (tmp);
+ tmp = array[i];
+ }
+ if (tmp->context!= array[j - 1]->context) {
+ array[j++] =dma_fence_get(tmp);
+ }
+ count = j;if (count == 0) {
tmp = dma_fence_allocate_private_stub(ktime_get());Regards,
Tvrtko
Quoted 8 lines
Regards,
Tvrtko
Quoted 3 lines
drivers/dma-buf/dma-fence-unwrap.c +1
-0+ }; if (count == 0) { tmp = dma_fence_allocate_private_stub(ktime_get());
PATCH 3/3 dma-buf: add selftest for fence order after merge
In reply to Christian KönigAdd a test which double checks that fences are in the expected order after a merge.
While at it also switch to using a mock array for the complex test instead of a merge.
--- drivers/dma-buf/st-dma-fence-unwrap.c | 69 ++++++++++++++++++++++++++- 1 file changed, 68 insertions(+), 1 deletion(-)
drivers/dma-buf/st-dma-fence-unwrap.c +68 -1
@@ -304,6 +304,72 @@ static int unwrap_merge(void *arg)return err; } +static int unwrap_merge_order (void *arg) +{ +struct dma_fence *fence, *f1, *f2, *a1, *a2, *c1, *c2; +struct dma_fence_unwrap iter; +int err =0 ; + + f1 =mock_fence (); +if (!f1) +return -ENOMEM ; + +dma_fence_enable_sw_signaling (f1); + + f2 =mock_fence (); +if (!f2) { +dma_fence_put (f1); +return -ENOMEM ; + } + +dma_fence_enable_sw_signaling (f2); + + a1 =mock_array (2 , f1, f2); +if (!a1) +return -ENOMEM ; + + c1 =mock_chain (NULL ,dma_fence_get (f1)); +if (!c1) + goto error_put_a1; + + c2 =mock_chain (c1,dma_fence_get (f2)); +if (!c2) + goto error_put_a1; + +/* +* The fences in the chain are the same as in a1 but in oposite order, +* the dma_fence_merge() function should be able to handle that. +*/ + a2 =dma_fence_unwrap_merge (a1, c2); + +dma_fence_unwrap_for_each (fence, &iter, a2) { +if (fence == f1) { + f1 =NULL ; +if (!f2) +pr_err ("Unexpected order!\n" ); + }else if (fence == f2) { + f2 =NULL ; +if (f1) +pr_err ("Unexpected order!\n" ); + }else { +pr_err ("Unexpected fence!\n" ); + err = -EINVAL ; + } + } + +if (f1 || f2) { +pr_err ("Not all fences seen!\n" ); + err = -EINVAL ; + } + +dma_fence_put (a2); +return err; + +error_put_a1: +dma_fence_put (a1); +return -ENOMEM ; +} +static int unwrap_merge_complex (void *arg) {struct dma_fence *fence, *f1, *f2, *f3, *f4, *f5;
@@ -327,7 +393,7 @@ static int unwrap_merge_complex(void *arg) goto error_put_f2;/* The resulting array has the fences in reverse */ - f4 =dma_fence_unwrap_merge (f2, f1); + f4 =mock_array (2 ,dma_fence_get (f2),dma_fence_get (f1));if (!f4) goto error_put_f3;
@@ -375,6 +441,7 @@ int dma_fence_unwrap(void)SUBTEST (unwrap_chain),SUBTEST (unwrap_chain_array),SUBTEST (unwrap_merge), +SUBTEST (unwrap_merge_order), SUBTEST(unwrap_merge_complex), };
Signature · 1 line
2.34.1