java-topology/defects/libevent/patch/libevent-0001-dispatch-callback-hashmap.md

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:

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

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