34 lines
1.3 KiB
Markdown
34 lines
1.3 KiB
Markdown
# dragonflybsd-0005 — CWE-407: devfs_find_device_by_name_worker — O(N) per /dev/ open
|
|
|
|
**Severity:** HIGH
|
|
**File:** `sys/vfs/devfs/devfs_core.c`
|
|
**Function:** `devfs_find_device_by_name_worker`
|
|
**CWE:** CWE-407 Algorithmic Complexity
|
|
|
|
## Defect
|
|
|
|
Two sequential `TAILQ_FOREACH` scans — `devfs_dev_list` by name, then `devfs_alias_list` by alias. O(N) per `/dev/` open or stat. Every device open goes through this path.
|
|
|
|
```c
|
|
/* scan 1: search by canonical name */
|
|
TAILQ_FOREACH(dev, &devfs_dev_list, link) {
|
|
if (strcmp(dev->si_name, name) == 0)
|
|
return dev;
|
|
}
|
|
|
|
/* scan 2: search by alias */
|
|
TAILQ_FOREACH(alias, &devfs_alias_list, link) {
|
|
if (strcmp(alias->name, name) == 0)
|
|
return alias->dev;
|
|
}
|
|
```
|
|
|
|
**Complexity:** O(N) per call where N = total device count. Called on every `open(2)` and `stat(2)` of a `/dev/` path.
|
|
|
|
## Scale
|
|
|
|
A system with 500 device entries incurs up to 1,000 string comparisons per device open. Under parallel workloads (e.g., parallel `open("/dev/urandom")` calls), this serializes under `devfs_lock` and creates contention.
|
|
|
|
## Fix
|
|
|
|
Hash tables keyed on device name string for both `devfs_dev_list` and `devfs_alias_list`. O(1) average per open. Hash table maintained on device creation/destruction which are already serialized under `devfs_lock`.
|