java-topology/docs/tickets/linux-0005-component-find-quadratic.md

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

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.

/* 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