[PATCH] dma-buf: Eliminate all duplicate fences in dma_fence_unwrap_merge

[Christian König]

Am 18.10.24 um 21:17 schrieb Friedrich Vock:
> [SNIP]
>>>           if (tmp) {
>>> -            array[count++] = dma_fence_get(tmp);
>>> +            for (j = 0; j < count; ++j) {
>>> +                if (array[count] == tmp)
>>> +                    break;
>>> +            }
>>> +            if (j == count)
>>> +                array[count++] = dma_fence_get(tmp);
>>
>> That is clearly not the right solution. Since comparing the context
>> should have already removed all duplicates.
>
> Sadly, not. This is true as long as the fences are ordered by context,
> but this is not a given. The error manifests precisely when they are not
> ordered.
>
> Imagine we try to merge two chains/arrays that contain the same 4 fences
> (I'll call them fences 1-4), but the second one has another fence with a
> higher context (fence 5) in front of it.

Yeah, the problem here is that the code originally assumed that we only 
merge arrays.

And most of those arrays were previously created by merging other 
fences, so they are supposed to be ordered.

>
> [SNIP]
>
> We can't assume the fences are in any sort of order w.r.t their context,
> so if we want to check for duplicates exhaustively we'll always end up
> with some kind of O(n^2) algorithm. I see only a handful of ways we 
> can go:
>
> a) Don't check exhaustively (current behavior). Obviously, this doesn't
> work that well in practice.
>
> b) Eat the O(n^2) cost (this patch). I've kept the current merging code
> since it's an easy way to reduce the amount of times we have to do the
> expensive duplicate check, but other than that I'm not sure we can do
> much to reduce cost.
>
> c) Enforce order w.r.t. context. I don't think we can require that fence
> chains order their fences by context, they should be ordered by timeline
> point (maybe it would work for arrays, but whatever). That leaves us
> with having to sort the fences by context just before merging. That
> would reduce complexity to some O(n log n) at worst, but in practice I
> fear it might not be worth it compared to just iterating over the result
> array a few times, especially given that once this bug is fixed, we
> should be back to only a few fences to merge :)

Yeah, how that happens is rather obvious and we indeed can't require 
fence chains to be ordered.

But I don't think we always need this O(n^2) cost either, we just need 
to check from the end of the array if we really have the highest context 
at hand.

That's still O(n^2) in the worst case, but for the case where we merge 
two sorted arrays it becomes O(1).

Give me a moment to hack that together.

Thanks,
Christian.

>
> Regards,
> Friedrich
>
>>
>> Going to double check the code.
>>
>> Thanks,
>> Christian.
>>
>>>               fences[sel] = dma_fence_unwrap_next(&iter[sel]);
>>>           }
>>>       } while (tmp);
>>> -- 
>>> 2.47.0
>>>
>>
>