# linux-0005: find_component — O(A×M×C) nested list scan per component_add()

**File:** `drivers/base/component.c`
**Function:** `find_component()` called from `find_components()`
**Severity:** HIGH — triggered on every `component_add()` for all aggregate devices
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)

## Code

```c
static int find_components(struct aggregate_device *adev)
{
    struct component_match *match = adev->match;
    size_t i;

    for (i = 0; i < match->num; i++) {                    // O(M) — match entries
        struct component_match_array *mc = &match->compare[i];
        struct component *c;

        c = find_component(adev, mc);                     // O(C) per entry
        if (!c) {
            adev->bound = false;
            return -ENXIO;
        }
        /* ... bind c ... */
    }
    return 0;
}

static struct component *find_component(struct aggregate_device *adev,
    struct component_match_array *mc)
{
    struct component *c;

    list_for_each_entry(c, &component_list, node) {       // O(C)
        if (c->adev && c->adev != adev)
            continue;
        if (mc->compare(c->dev, mc->data))
            return c;
    }
    return NULL;
}
```

`find_components()` is called from `try_to_bring_up_masters()`, which runs on
every `component_add()` for all aggregate devices.  With A aggregate devices,
M match entries each, and C registered components: O(A × M × C) per add.

## Complexity

| Variable | Meaning |
|----------|---------|
| A | Number of aggregate devices registered |
| M | Number of match entries per aggregate device |
| C | Total registered components |

Example: A=10 aggregate devices (DRM, IOMMU, sound, USB controllers), each
matching M=20 sub-components from a pool of C=200 registered components.
Every `component_add()` triggers 10 × 20 × 200 = **40,000 list comparisons**.

## When Triggered

- Driver probe: every device that calls `component_add()` triggers a full
  `try_to_bring_up_masters()` scan across all aggregate devices.
- Platform drivers with many components (e.g., display subsystems on SoCs with
  10+ display engines, DSI controllers, MIPI PHYs): every component probe hits
  the full O(A × M × C) scan.
- Embedded/automotive platforms with large component graphs see this at boot.

## Root Cause

`component_list` is a flat linked list with no secondary index.  `find_component()`
has no choice but to walk it linearly.  The match criterion is typically the device
pointer (`mc->data == c->dev` for `compare_dev`), which is a direct pointer
comparison — an ideal hash key that is never exploited.

## Fix

Add a `DECLARE_HASHTABLE(component_dev_ht, 8)` in the module (256 buckets).
Key: `(unsigned long)dev >> 3` (strip alignment bits).
Each `struct component` gains `struct hlist_node dev_hash`.

`find_component()` attempts O(1) hash lookup first; falls back to O(C) list walk
only for non-pointer compare functions.  `component_add()` inserts into hash;
`component_del()` removes.

```c
/* Fast path — O(1) for compare_dev / compare_of */
if (mc->compare && mc->data) {
    unsigned long key = (unsigned long)mc->data >> 3;
    hash_for_each_possible(component_dev_ht, c, dev_hash, key) {
        if (c->adev && c->adev != adev) continue;
        if (mc->compare(c->dev, mc->data)) return c;
    }
}
/* Slow fallback — O(C) for exotic comparators */
list_for_each_entry(c, &component_list, node) { ... }
```

## Impact

- SoC display drivers: 10+ components, 5+ aggregate devices → O(10×5×10) = 500
  comparisons per component probe versus O(1) with hash.
- At boot with 50 components: 50 probe events × 10 adevs × 20 matches × 50 comps
  = 500,000 comparisons without the fix.
- With fix: 50 probe events × 10 × 20 × O(1) = 10,000 hash probes.

## Patch

See `defects/linux/patch/linux-0005-component-find-quadratic.patch`