30 lines
1.2 KiB
Markdown
30 lines
1.2 KiB
Markdown
# hurd-0002 — CWE-407: ports_interrupt_rpc_on_notification — O(N) linked list scan per RPC
|
||
|
||
**Severity:** MEDIUM
|
||
**File:** `libports/interrupt-on-notify.c` lines ~63–74
|
||
**Function:** `ports_interrupt_rpc_on_notification`
|
||
**CWE:** CWE-407 Algorithmic Complexity
|
||
|
||
## Defect
|
||
|
||
Linear scan of `_ports_notifications` (global linked list) on every RPC notification setup, while holding `_ports_lock`. Second linear scan over `rpc->notifies` for duplicate check.
|
||
|
||
```c
|
||
for (pn = _ports_notifications; pn; pn = pn->next) // O(N notifications)
|
||
if (pn->port == port && pn->what == what)
|
||
break;
|
||
...
|
||
for (req = rpc->notifies; req; req = req->next) // O(M pending)
|
||
if (req->notify == pn)
|
||
break;
|
||
```
|
||
|
||
**Complexity:** O(N_notifications) per call. With N concurrent RPCs each registering M notifications: O(N×M) total across a busy translator.
|
||
|
||
## Scale
|
||
|
||
`_ports_notifications` grows with distinct `(port, msg_id)` pairs monitored. In `ext2fs` with many simultaneous readers this list is long. Called per RPC setup in `libdiskfs` and `libtrivfs`.
|
||
|
||
## Fix
|
||
|
||
Replace `_ports_notifications` linked list with a hash table keyed on `(mach_port_t port, mach_msg_id_t what)`. O(1) lookup replaces O(N) scan.
|