Created attachment 225274 [details] [review]
Do not hang on caps intersect when the caps have duplicated entries

After some investigation, the issue happens when caps with duplicated entries are intersected. gst_caps_intersect_full will be called from gst_base_transform and will hang on gst_structure_intersect, resulting in a caps with many duplicated lists inside lists entries.

This happened cause the gamma element set it caps tempĺate to     GST_STATIC_CAPS (GST_VIDEO_CAPS_MAKE ("{ AYUV, "
            "ARGB, BGRA, ABGR, RGBA, ABGR, RGBA, Y444, "
            "xRGB, RGBx, xBGR, BGRx, RGB, BGR, Y42B, NV12, "
            "NV21, YUY2, UYVY, YVYU, I420, YV12, IYUV, Y41B }"))
where RGBA and ABGR are duplicated entries. 

After caps negotiation finally finishes, the result is:
video/x-raw, format=(string){ I420, YV12, YUY2, UYVY, AYUV, RGBx, BGRx, xRGB, xBGR, { RGBA, RGBA, { RGBA, RGBA }, { RGBA, RGBA, { RGBA, RGBA } }, { RGBA, RGBA, { RGBA, RGBA }, { RGBA, RGBA, { RGBA, RGBA } } }, { RGBA, RGBA, { RGBA, RGBA }, { RGBA, RGBA, { RGBA, RGBA } }, { RGBA, RGBA, { RGBA, RGBA }, { RGBA, RGBA, { RGBA, RGBA } } } }, { RGBA, RGBA, { RGBA, RGBA }, { RGBA, RGBA,...

Fixing gstgamma also fixes the issue, but a more generic fix is attached.

FYI to reproduce the original issue you should revert this patch in -good:

commit 25803d651bf75ee1c2c0d728962ed93a5254eee8
Author: Andre Moreira Magalhaes (andrunko) <andre.magalhaes@collabora.co.uk>
Date:   Thu Sep 27 15:50:49 2012 -0300

    gamma: remove duplicate entries at format at caps
    
    Avoids extra caps/structures processing

I'm wondering if it shouldn't be:

diff --git a/gst/gstvalue.c b/gst/gstvalue.c
index 80c59fe..de9fa06 100644
--- a/gst/gstvalue.c
+++ b/gst/gstvalue.c
@@ -3498,7 +3498,7 @@ gst_value_intersect_list (GValue * dest, const GValue * value1,
 
         gst_value_init_and_copy (&temp, dest);
         g_value_unset (dest);
-        gst_value_list_concat (dest, &temp, &intersection);
+        gst_value_list_merge (dest, &temp, &intersection);
         g_value_unset (&temp);
       }
       g_value_unset (&intersection);

which avoids duplicates in dest.

(In reply to comment #3)
> I'm wondering if it shouldn't be:
> 
> diff --git a/gst/gstvalue.c b/gst/gstvalue.c
> index 80c59fe..de9fa06 100644
> --- a/gst/gstvalue.c
> +++ b/gst/gstvalue.c
> @@ -3498,7 +3498,7 @@ gst_value_intersect_list (GValue * dest, const GValue *
> value1,
> 
>          gst_value_init_and_copy (&temp, dest);
>          g_value_unset (dest);
> -        gst_value_list_concat (dest, &temp, &intersection);
> +        gst_value_list_merge (dest, &temp, &intersection);
>          g_value_unset (&temp);
>        }
>        g_value_unset (&intersection);
> 
> which avoids duplicates in dest.

Test here and it works with both this patch or my patch from comment #1.

Merging however requires to always iterate over the complete list while concat is just changing a few pointers.

I still think this change is correct, just has the potential of degraded performance in other cases.

I think it's the right thing to do as well, and I hope the positive effects of keeping the list small right away will outweigh the negatives overall:


commit 507fc9cea7d587446fba08dfeac7e063e14c680e
Author: Tim-Philipp Müller <tim.muller@collabora.co.uk>
Date:   Sat Sep 29 14:35:58 2012 +0100

    value: avoid duplicates when intersecting lists
    
    Fixes negotiation taking a ridiculous amount of
    time (multiple 10s of seconds on a core2) when
    there are duplicate entries in lists.
    
    Could have a negative performance impact on other
    scenarios because we now have to iterate the
    dest list to avoid duplicates, but we don't
    have a lot of lists any more these days, and
    they tend to be small anyway. The negatives
    are hopefully countered by the positive effects
    of reducing the list length early on in the
    process. And in any case, it's the right thing
    to do.
    
    Based on patch by Andre Moreira Magalhaes.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=684981

Comment on attachment 225274 [details] [review]
Do not hang on caps intersect when the caps have duplicated entries

I've pushed my patch now, because it's more generic.