Skip to contentSkip to conversation

Fix Fix fence merge handling

PATCH In review Christian König 4 participants 19 messages Oct 24, 2024 – Nov 8, 2024

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

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.

#1 lore raw

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
index 8a08ffde31e7..46ac42bcfac0 100644
@@ -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
Reviewed-by on v1 1/3
#2 lore raw

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_array leading 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 of kzalloc(). This patch here does the later.

This patch seems reasonable to me if the above use is in fact valid.

Quoted 2 lines

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
index 8a08ffde31e7..46ac42bcfac0 100644
@@ -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
#3 lore raw

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_array leading to a warning from

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_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 of kzalloc(). This patch here does the later.

This patch seems reasonable to me if the above use is in fact valid.

Quoted 2 lines

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 -4
index 8a08ffde31e7..46ac42bcfac0 100644
@@ -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

#4 lore raw

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_array leading 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_merge failed 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,
Friedrich

Quoted 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 of kzalloc(). This patch here does the later.

This patch seems reasonable to me if the above use is in fact valid.

Quoted 2 lines

Fixes tag?

Patch itself LGTM:

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
index 8a08ffde31e7..46ac42bcfac0 100644
@@ -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
#5 lore raw

Re: [PATCH 1/3] dma-buf/dma-fence_array: use kvzalloc

In reply to Christian König
Quoted 10 lines · Christian König

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.

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
---
  drivers/dma-buf/dma-fence-array.c | 6 +++---
  1 file changed, 3 insertions(+), 3 deletions(-)
drivers/dma-buf/dma-fence-array.c +3 -3
index 8a08ffde31e7..46ac42bcfac0 100644
@@ -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);
 
#6 lore raw

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_array leading to a warning from kzalloc() 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 of kzalloc(). 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.

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

---
  drivers/dma-buf/dma-fence-array.c | 6 +++---

  1 file changed, 3 insertions(+), 3 deletions(-)
drivers/dma-buf/dma-fence-array.c +3 -3
index 8a08ffde31e7..46ac42bcfac0 100644
@@ -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);

#7 lore raw

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_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.

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 (see 0829b5bcdd3b ("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

---
  drivers/dma-buf/dma-fence-array.c | 6 +++---

  1 file changed, 3 insertions(+), 3 deletions(-)
drivers/dma-buf/dma-fence-array.c +3 -3
index 8a08ffde31e7..46ac42bcfac0 100644
@@ -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);

#8 lore raw

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_array leading to a warning from kzalloc() 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 of kzalloc(). 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.

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

---
  drivers/dma-buf/dma-fence-array.c | 6 +++---

  1 file changed, 3 insertions(+), 3 deletions(-)
drivers/dma-buf/dma-fence-array.c +3 -3
index 8a08ffde31e7..46ac42bcfac0 100644
@@ -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);

#9 lore raw

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_array leading to a warning from kzalloc() 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 of kzalloc(). 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.

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

---
  drivers/dma-buf/dma-fence-array.c | 6 +++---

  1 file changed, 3 insertions(+), 3 deletions(-)
drivers/dma-buf/dma-fence-array.c +3 -3
index 8a08ffde31e7..46ac42bcfac0 100644
@@ -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);

#10 lore raw

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_array leading to a warning from kzalloc() 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 of kzalloc(). 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.

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

---
  drivers/dma-buf/dma-fence-array.c | 6 +++---

  1 file changed, 3 insertions(+), 3 deletions(-)
drivers/dma-buf/dma-fence-array.c +3 -3
index 8a08ffde31e7..46ac42bcfac0 100644
@@ -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);

#11 lore raw

PATCH 2/3 dma-buf: sort fences in dma_fence_unwrap_merge

In reply to 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.

---
 drivers/dma-buf/dma-fence-unwrap.c | 39 ++++++++++++++++++++++++++----
 1 file changed, 34 insertions(+), 5 deletions(-)
drivers/dma-buf/dma-fence-unwrap.c +34 -5
index 628af51c81af..d9aa280d9ff6 100644
@@ -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
#12 lore raw

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.

---
  drivers/dma-buf/dma-fence-unwrap.c | 39 ++++++++++++++++++++++++++----
  1 file changed, 34 insertions(+), 5 deletions(-)
drivers/dma-buf/dma-fence-unwrap.c +2 -4
index 628af51c81af..d9aa280d9ff6 100644
@@ -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());
#13 lore raw

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.

---
  drivers/dma-buf/dma-fence-unwrap.c | 39 ++++++++++++++++++++++++++----

  1 file changed, 34 insertions(+), 5 deletions(-)
drivers/dma-buf/dma-fence-unwrap.c +1 -1
index 628af51c81af..d9aa280d9ff6 100644
@@ -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,
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());

#14 lore raw

Re: [PATCH 2/3] dma-buf: sort fences in dma_fence_unwrap_merge

In reply to Christian König
Quoted 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.

---
  drivers/dma-buf/dma-fence-unwrap.c | 39 ++++++++++++++++++++++++++----
  1 file changed, 34 insertions(+), 5 deletions(-)
drivers/dma-buf/dma-fence-unwrap.c +23 -5
index 628af51c81af..d9aa280d9ff6 100644
@@ -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());
#15 lore raw

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.

---
  drivers/dma-buf/dma-fence-unwrap.c | 39 ++++++++++++++++++++++++++----

  1 file changed, 34 insertions(+), 5 deletions(-)
drivers/dma-buf/dma-fence-unwrap.c +1 -1
index 628af51c81af..d9aa280d9ff6 100644
@@ -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.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.

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
index 628af51c81af..47d67e482e96 100644
@@ -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());
#16 lore raw

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.

---
  drivers/dma-buf/dma-fence-unwrap.c | 39
++++++++++++++++++++++++++----

  1 file changed, 34 insertions(+), 5 deletions(-)
drivers/dma-buf/dma-fence-unwrap.c +1 -1
index 628af51c81af..d9aa280d9ff6 100644
@@ -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.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.

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_merge

drivers/dma-buf/dma-fence-unwrap.c +1 -0
index 628af51c81af..47d67e482e96 100644
@@ -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 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;

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());
#17 lore raw

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.

---
  drivers/dma-buf/dma-fence-unwrap.c | 39
++++++++++++++++++++++++++----

  1 file changed, 34 insertions(+), 5 deletions(-)
drivers/dma-buf/dma-fence-unwrap.c +1 -1
index 628af51c81af..d9aa280d9ff6 100644
@@ -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.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.

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_merge

drivers/dma-buf/dma-fence-unwrap.c +1 -0
index 628af51c81af..47d67e482e96 100644
@@ -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 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;

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());
#18 lore raw

PATCH 3/3 dma-buf: add selftest for fence order after merge

In reply to Christian König

Add 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
index f0cee984b6c7..876eabddb08f 100644
@@ -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