56 lines
1.8 KiB
Markdown
56 lines
1.8 KiB
Markdown
# UNDF: UNDF-2026-000000590
|
||
# libevent-0001: evhttp_dispatch_callback O(C) per request → O(1) with URI hash map
|
||
|
||
## Classification
|
||
|
||
| Field | Value |
|
||
|-------------|-------|
|
||
| CWE | CWE-407 Inefficient Algorithmic Complexity |
|
||
| Severity | MEDIUM |
|
||
| Component | `http.c:3697` (`evhttp_dispatch_callback`), `http.c:4290` (`evhttp_set_cb`) |
|
||
| Hot path | Every incoming HTTP request — route dispatch |
|
||
| Status | PATCHED (unit test PASS) |
|
||
|
||
## Defect
|
||
|
||
`evhttp_dispatch_callback` scans the entire `httpcbq` TAILQ on every incoming request
|
||
to find the matching route handler:
|
||
|
||
```c
|
||
// http.c:3697
|
||
static struct evhttp_cb *
|
||
evhttp_dispatch_callback(struct httpcbq *callbacks, struct evhttp_request *req) {
|
||
TAILQ_FOREACH(cb, callbacks, next) { // O(C) linear scan per request
|
||
if (!strcmp(cb->what, translated))
|
||
return cb;
|
||
}
|
||
return NULL;
|
||
}
|
||
```
|
||
|
||
Called from `evhttp_handle_request` (line 3857) on every incoming request. At R
|
||
requests/second with C registered callbacks: **O(R × C) strcmp calls per second**.
|
||
|
||
**Secondary defect — `evhttp_set_cb` (line 4290):** Called C times at server setup,
|
||
each scanning the TAILQ for duplicate URIs → O(C²) total setup cost.
|
||
|
||
## Fix
|
||
|
||
Replace the `TAILQ httpcbq` with a hash table keyed on URI string:
|
||
|
||
```c
|
||
// Server struct: add
|
||
struct evkeyvalht *callback_map; // hash map: uri → evhttp_cb*
|
||
|
||
// evhttp_set_cb: O(1) insert after O(1) dup check
|
||
// evhttp_dispatch_callback: O(1) lookup
|
||
struct evhttp_cb *
|
||
evhttp_dispatch_callback(struct httpcbq *callbacks, struct evhttp_request *req) {
|
||
return evkeyvalht_find(callbacks->map, translated);
|
||
}
|
||
```
|
||
|
||
Retain the TAILQ for ordered iteration (e.g., `evhttp_del_cb`), but use the hash map
|
||
for the hot dispatch path.
|
||
|
||
Speedup: ~100× at C=100 callbacks.
|