# 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):

```c
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):

```c
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.
