engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/docs/tickets/dragonflybsd-0004.md

1.1 KiB
Raw Permalink Blame History

dragonflybsd-0004 — CWE-407: devfs_destroy_related_worker — O(N×C) restart-on-match scan

Severity: MEDIUM File: sys/vfs/devfs/devfs_core.c Function: devfs_destroy_related_worker CWE: CWE-407 Algorithmic Complexity

Defect

TAILQ_FOREACH over global devfs_dev_list with goto restart on each child found. O(N×C) where N=total devices, C=children of needle. Triggered on device detach (USB removal etc.).

restart:
TAILQ_FOREACH(dev, &devfs_dev_list, link) {
    if (dev->si_parent == needle) {
        devfs_destroy_dev_worker(dev);
        goto restart;   // O(N) scan again for next child
    }
}

Complexity: O(N×C) where N = total devices in devfs_dev_list, C = number of children of the target device.

Scale

A USB hub with 10 child devices on a system with 500 devfs entries incurs 5,000 list-walk steps per detach event. Cascading hub removal multiplies this further.

Fix

Collect-then-destroy: single O(N) pass to collect all matching children into a local list, then destroy each without restarting the scan. Eliminates goto restart entirely.