UNDF: UNDF-2026-000000685

UNDF: (pending)

gstreamer-0002: `gst_input_selector_event` — O(N²) `g_list_find` on `pushed_pads`

CWE-407 — Algorithmic Complexity

Field	Value
ID	gstreamer-0002
Severity	MEDIUM
Ecosystem	GStreamer
File	`subprojects/gstreamer/plugins/elements/gstinputselector.c`
Lines	1806–1887 (function `gst_input_selector_event`)
Complexity	O(N²) where N = number of sink pads
Hot path	Every upstream event dispatched through an inputselector element

Defect

gst_input_selector_event() dispatches an event to all sink pads exactly once, using a GList *pushed_pads as a seen-set. For every pad returned by the iterator it calls g_list_find(pushed_pads, eventpad) which is O(N):

static gboolean
gst_input_selector_event (GstPad * pad, GstObject * parent, GstEvent * event)
{
  ...
  GList *pushed_pads = NULL;

  iter = gst_element_iterate_sink_pads (GST_ELEMENT_CAST (sel));

  /* push to active sinkpad first */
  if (sel->active_sinkpad) {
    eventpad = gst_object_ref (sel->active_sinkpad);
    ...
    result |= gst_pad_push_event (eventpad, event);
    pushed_pads = g_list_append (pushed_pads, eventpad);   /* O(N) append */
    gst_object_unref (eventpad);
  }

  while (!done) {
    switch (gst_iterator_next (iter, &item)) {
      case GST_ITERATOR_OK:
        eventpad = g_value_get_object (&item);

        /* if already pushed, skip */
        if (g_list_find (pushed_pads, eventpad)) {         /* O(N) scan */
          g_value_reset (&item);
          break;
        }

        gst_event_ref (event);
        result |= gst_pad_push_event (eventpad, event);
        pushed_pads = g_list_append (pushed_pads, eventpad); /* O(N) append */
        ...
    }
  }
  g_list_free (pushed_pads);
  ...
}

With N sink pads the event dispatch is O(N²): N iterations × O(N) scan each. This function is called on every upstream event (EOS, FLUSH, SEGMENT, CAPS, etc.). Pipelines with many input selector pads (e.g., live A/V switching with dozens of sources) will see quadratic growth in event handling latency.

Fix

Replace GList *pushed_pads with a GHashTable *pushed_pads_set using pointer identity (g_direct_hash / g_direct_equal). GHashTable lookup is O(1) average, reducing the whole function to O(N):

static gboolean
gst_input_selector_event (GstPad * pad, GstObject * parent, GstEvent * event)
{
  GstInputSelector *sel;
  gboolean result = FALSE;
  GstIterator *iter;
  gboolean done = FALSE;
  GValue item = { 0, };
  GstPad *eventpad;
  /* CWE-407 fix: O(1) membership test via pointer-identity hash set */
  GHashTable *pushed_pads_set = g_hash_table_new (g_direct_hash, g_direct_equal);

  sel = GST_INPUT_SELECTOR (parent);
  iter = gst_element_iterate_sink_pads (GST_ELEMENT_CAST (sel));

  g_rw_lock_reader_lock (&sel->active_sinkpad_lock);
  GST_INPUT_SELECTOR_LOCK (sel);
  if (GST_EVENT_IS_SERIALIZED (event) && GST_EVENT_IS_DOWNSTREAM (event))
    gst_input_selector_maybe_commit_active_pad (sel);

  if (sel->active_sinkpad) {
    eventpad = gst_object_ref (sel->active_sinkpad);
    GST_INPUT_SELECTOR_UNLOCK (sel);

    gst_event_ref (event);
    result |= gst_pad_push_event (eventpad, event);
    g_hash_table_add (pushed_pads_set, eventpad);          /* O(1) insert */
    gst_object_unref (eventpad);
  } else {
    GST_INPUT_SELECTOR_UNLOCK (sel);
  }

  g_rw_lock_reader_unlock (&sel->active_sinkpad_lock);

  while (!done) {
    switch (gst_iterator_next (iter, &item)) {
      case GST_ITERATOR_OK:
        eventpad = g_value_get_object (&item);

        /* if already pushed, skip — O(1) hash lookup */
        if (g_hash_table_contains (pushed_pads_set, eventpad)) {
          g_value_reset (&item);
          break;
        }

        gst_event_ref (event);
        result |= gst_pad_push_event (eventpad, event);
        g_hash_table_add (pushed_pads_set, eventpad);      /* O(1) insert */

        g_value_reset (&item);
        break;
      case GST_ITERATOR_RESYNC:
        gst_iterator_resync (iter);
        break;
      case GST_ITERATOR_ERROR:
        GST_ERROR_OBJECT (pad, "Could not iterate over sinkpads");
        done = TRUE;
        break;
      case GST_ITERATOR_DONE:
        done = TRUE;
        break;
    }
  }
  g_value_unset (&item);
  gst_iterator_free (iter);
  g_hash_table_destroy (pushed_pads_set);                  /* replaces g_list_free */

  gst_event_unref (event);
  return result;
}

Speedup

Sink pads	Before (comparisons)	After (hash ops)	Ratio
10	55	10	5.5×
50	1,275	50	25.5×
100	5,050	100	50.5×
200	20,100	200	~100×

Real-world impact: a live sports switching pipeline with 64 camera feeds dispatches EOS/FLUSH/SEGMENT events O(N²) = 2,080 comparisons per event. Patched: 64 hash ops. With hundreds of events per second the cumulative overhead is significant at scale.

4.9 KiB Raw Permalink Blame History Unescape Escape